Practice on Toph

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

Perhaps Strings Are Inevitable

By Hasinur_ · 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

Discussion

Statistics


75% Solution Ratio

samiulsamiEarliest, 1M ago

likhon5Fastest, 0.1s

likhon5Lightest, 337 MB

serotoninShortest, 1524B

Submit

Login to submit

Editorial

As we can not update all the strings that have prefix PPPfor each update query, we can hold the upda...

Toph uses cookies. By continuing you agree to our Cookie Policy.