# Perhaps Strings Are Inevitable

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