D. Whalica's Lottery Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Whalica has $$$n$$$ fans who are invited to join Whalica's lottery game.

Whalica stipulates that only non-empty strings consisting only of the characters $$$\mathtt{a, c, h, i, l, w}$$$ can be winning strings. Before the game starts, each fan writes down a valid guess string $$$s_i$$$.

There are $$$q$$$ events in total. For the $$$i$$$-th event, one of the following happens:

  1. Whalica conducts a draw. Whalica provides a valid winning string $$$T_i$$$, and then reads out each character of this string from left to right. Let $$$s[l, r]$$$ denote the string formed by concatenating the characters $$$s_l, s_{l + 1}, \cdots, s_{r - 1}, s_r$$$ from $$$s$$$ in order. When Whalica reads the $$$j$$$-th character $$$T_{i,j}$$$, every fan $$$k$$$ such that $$$s_k[1, j] = T_i[1, j]$$$ (i.e., the first $$$j$$$ characters of the fan's guess string match the first $$$j$$$ characters of the winning string) receives $$$1$$$ Whalica coin. Formally, the number of Whalica coins fan $$$k$$$ gets in this draw is $$$\operatorname{LCP}(s_k, T_i)$$$, where $$$\operatorname{LCP}(s, t)$$$ denotes the length of the longest common prefix of strings $$$s, t$$$.
  2. Fans modify their strings. To prevent the game from becoming monotonous, Whalica requires every fan to change their guess string. However, the fans have secretly expressed their affection for Whalica in their strings and are unwilling to make significant changes. Specifically, they do not change the length of their guess strings, but they perform one replacement on each character of their guess string, following the cyclic rule: $$$\mathtt{w \to h \to a \to l \to i \to c \to w}$$$. For example, if a fan's string is $$$\mathtt{whalica}$$$, after modification it becomes $$$\mathtt{halicwl}$$$.

Whalica is too lazy and just wants to rest. Can you help her compute how many Whalica coins she needs to pay out for each draw event?

Input

The first line contains two integers $$$n$$$, $$$q$$$ $$$(1 \le n, q \le 10^5)$$$ — the number of fans and the number of events.

Each of the next $$$n$$$ lines contains a fan's initial guess string $$$s_i$$$ $$$(1 \le |s_i| \le 10^5)$$$.

Each of the next $$$q$$$ lines contains an integer $$$op_i \in \{1,2\}$$$ — the event type.

  • If $$$op_i = 1$$$, it is a draw event. The same line also contains a string $$$T_i$$$ $$$(1 \le |T_i| \le 10^5)$$$ — the winning string.
  • If $$$op_i = 2$$$, it is a modification event.

It is guaranteed that the total sum of $$$|s_i|$$$ and the total sum of $$$|T_i|$$$ do not exceed $$$10^5$$$, and that the character set of all strings is a subset of $$$\{\mathtt{a,c,h,i,l,w}\}$$$.

Output

For each draw event, output the total number of Whalica coins Whalica needs to pay out.

Example
Input
3 3
awa
awhlica
alicawhalica
1 awc
2
1 licwlaawwl
Output
5
7