Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fabby and Her Wedding Dress

By Hasinur_ · Limits 4s, 256 MB

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.

  • 1st type of query: Two integers $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.
  • 2nd type of query: A string $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$.

Input

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$.

Output

For each query of type 2, print the beauty of $T$ in a line.

Sample

InputOutput
2
abcd
abde
2
1 2 3 c
2 abc
2

Discussion

Statistics


57% Solution Ratio

mh755628Earliest, 1M ago

kzvd4729Fastest, 0.1s

BrehamPieLightest, 13 MB

mh755628Shortest, 1958B

Submit

Login to submit

Editorial

This problem can be solved with $Heavy-Light$ trick. Split the input strings (Chander Buri's s...

Related Contests