Note

Problem Statement

You are given $N$ strings, and the $i$-th string is denoted by $S_i$.
Process $Q$ queries in order. Each query is one of the following $2$ types.

• 1 x c: Append the character $c$ to the end of $S_x$.
• 2 x: For each $k\ (1 \leq k \leq N)$, find the length of the longest common prefix of $S_x,S_k$, and answer the sum of these lengths.

Input

$N$
$S_1$
$S_2$
$\vdots$
$S_N$
$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

$1\ \ x\ \ c$

$2\ \ x$

• $1 \leq N,Q \leq 2\times 10^5$
• $N,Q$ are integers
• $S_i$ is a string of at least $1$ character consisting of lowercase English letters
• $\displaystyle \sum_{i=1}^N |S_i| \leq 2\times 10^5$ (before processing the queries)
• $1 \leq x \leq N$
• $c$ is a lowercase English letter
• There is at least $1$ query of the $2$nd type

Output

For all queries of the $2$nd type, output the answer in order, each followed by a newline.

Sample

3
a
abc
abcde
4
1 1 b
2 2
1 2 d
2 3

8
11