Perhaps Strings Are Inevitable

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

2
abcdx
abcex
3
1 abce d
2 abce
2 abcd

0
2