Perhaps Strings Are Inevitable

Hasinur_ Replay of National Girls'...
Limits 1s, 1.0 GB

Strings are inevitable in life. They give meaning to our expressions. Strings come in life in many ways, like a well-written letter for hearts, a nice song composed to heal the souls. For NGPC contestants like you, strings come in the form of a programming problem to give joy.

You will be given a list L\textbf{L} of N\textbf{N} strings and M\textbf{M} queries. The queries are of two types. They are described below:

  • Type 1: A prefix PP and a character CC will be given. You will have to change the (P1)th(|P| - 1)^{th} character to CC of the strings which have a prefix PP. Note that, we start counting indexes of strings from 00.

  • Type 2: A prefix SS will be given. You have to determine the number of strings that have a prefix that matches with SS.

A prefix of a string TT is a substring of TT that occurs at the beginning of TT.

Input

The first line of the input file will contain a single positive integer N\textbf{N} (1N105)(1 \leq N \leq 10^{5}) which denotes the number of strings in the list L\textbf{L}. Each of the next NN lines will contain a string Li\textbf{L}_{i} (1Li105)(1 \leq |L_{i}| \leq 10^{5}). After that, there will be a single positive integer M\textbf{M} (1M105)(1 \leq M \leq 10^{5}). Each of the next MM lines will contain each of the two types of queries described below:

  • 11 PP CC
    This is the first type of query. You will have to change the (P1)th(|P| - 1)^{th} character to CC of the strings which have a prefix Q\textbf{Q} such that QQ == PP.
    Here, 1P1051 \leq |P| \leq 10^{5} and CC contains one of the lowercase English alphabets (az)(‘a’ - ‘z’) only.

  • 22 SS
    This is the second type of query. You have to determine the number of strings that have a prefix that matches with SS.
    Here, 1S1051\leq |S| \leq 10^{5}.

It is guaranteed that all the strings in the input file contains lowercase English alphabets (az)(‘a’ - ‘z’) only and there will be at least one query of type 2.

Other constraints:
1i=1NLi3×1061\leq \sum_{i=1}^{N} |L_{i}|\leq 3 \times 10^{6}

1Pi+Si3×1061\leq \sum |P_{i}| + \sum|S_{i}|\leq 3 \times 10^{6}

Output

For each of the 2nd2^{nd} type of query, print the number of strings which have a prefix that matches with given prefix SS.

Sample

InputOutput
2
abcdx
abcex
3
1 abce d
2 abce
2 abcd
0
2

Submit

Login to submit.

Statistics

75% Solution Ratio
samiulsamiEarliest, 8M ago
likhon5Fastest, 0.1s
likhon5Lightest, 337 MB
serotoninShortest, 1524B
Toph uses cookies. By continuing you agree to our Cookie Policy.