# 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 $\textbf{L}$ of $\textbf{N}$ strings and $\textbf{M}$ queries. The queries are of two types. They are described below:

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

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

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

## Input

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

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

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

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

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

$1\leq \sum |P_{i}| + \sum|S_{i}|\leq 3 \times 10^{6}$

## Output

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

## Sample

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

0
2


### Statistics

75% Solution Ratio

samiulsamiEarliest, 1M ago

likhon5Fastest, 0.1s

likhon5Lightest, 337 MB

serotoninShortest, 1524B