注意

問題文

$N$ 個の文字列が与えられ、$i$ 番目の文字列を $S_i$ とします。
$Q$ 個のクエリを順番に処理してください。クエリは次の $2$ 種類のいずれかです。

• 1 x c: $S_x$ の末尾に文字 $c$ を追加する。
• 2 x: 各 $k\ (1 \leq k \leq N)$ について $S_x,S_k$ の最長共通接頭辞の長さを求め、それらの総和を答える。

入力

$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$ は整数
• $S_i$ は英小文字から成る $1$ 文字以上の文字列
• $\displaystyle \sum_{i=1}^N |S_i| \leq 2\times 10^5$ (クエリ処理前)
• $1 \leq x \leq N$
• $c$ は英小文字
• $2$ 種類目のクエリが $1$ つ以上存在する

出力

全ての $2$ 種類目のクエリに対して、順番に答えを出力し改行してください。

サンプル

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

8
11