You all remember Fabby, the princess of Byteland. People of Byteland are waiting for the biggest celebration ever as the wedding ceremony of Fabby is near. The royal family and the princess are happy too. To make the wedding memorable, she wants her wedding dress to be exceptional. She wants the dress to be prepared by Chander Buri (Fairy of the moon). One fairy night, there was a gentle breeze and she went to the window. Looking to the full moon, she asked Chander Buri to make a wedding dress full of beautiful strings.
Chander Buri listened to the whisper and gave her some strings from her list. She asked the princess to make some queries which will change the strings in the list. The princess can also choose her beautiful string $T$ and measure the beauty. The beauty of $T$ is defined as the number of strings in Chander Buri's list which has a prefix $P = T$. Chander Buri will compose the wedding dress with the most beautiful string.
You are a great programmer and you are hired to solve the problem for her. You will be given the list of strings $S$ that Chander Buri possesses. Then there will be $Q$ queries.
$i, j$ and a character $C$ will be given. You have to change $S_{ij}=C$. Here, $S_{ij}$ means ${j}^{\text{th}}$ character of the ${i}^{\text{th}}$ string in the list.$T$ will be given. You have to calculate the beauty of $T$. That means, you have to count how many strings $S_{i}$ are there in the list ${S}$ such that $S_{i}$ has a prefix $P=T$.The first line of the input will contain an integer $N (1\leq N \leq 2 \times 10^5)$, the number of strings in the list.
Each of the next $N$ lines will contain a string $S_{i} (1\leq |S_i| \leq 2 \times 10^5)$, the list of strings to be considered. $S_{i} $ contains lowercase English alphabets only.
After that, there will be an integer $Q (1\leq Q \leq 2 \times 10^5)$, the number of queries.
Each of the next $Q$ lines will contain the description of the query:
$1 \,\, i \,\, j \,\, C$ $1$ denotes first type of query and you have to change $S_{ij}=C$. Here, $1\leq i \leq N; 1\leq j \leq |S_i|$. Character $C$ contains lowercase English alphabets only.$2 \, \, T$ $2$ denotes second type of query as described in the statement. Here, $1\leq |T_i| \leq 2 \times 10^5$. String $T$ contains lowercase English alphabets only.The sum of the length of $S_i$ over all the strings in the list will not exceed $ 2 \times 10^5$. Similarly, the sum of the length of $T_i$ over all queries will not exceed $ 2 \times 10^5$.
For each query of type 2, print the beauty of $T$ in a line.
| Input | Output |
|---|---|
2 abcd abde 2 1 2 3 c 2 abc | 2 |