問題文

英小文字からなる長さ $L$ の文字列が $N$ 個与えられます。 $i = 1, 2, \ldots, N$ について、 $i$ 番目の文字列を $S_i$ とします。

以下のようなクエリが $Q$ 個与えられるので、順番に処理してください。

• 1 k c d: 整数 $k$ 、文字 $c, d$ が与えられる。 $S$ に含まれるすべての文字列について、 $k$ 文字目を $c$ から $d$ に変更する。ただし、 $k$ 文字目が $c$ でないものには何もしない。
• 2 t: 文字列 $t$ が与えられる。整数 $i$ であって、 $t$ が $S_i$ の接頭辞になるものの個数を答える。

入力

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

• $N, L, Q$ は整数
• $1 \le N \le 1000$
• $1 \le L \le 3000$
• $1 \le Q \le 4000$
• $S_i$ は英小文字からなる文字列
• $|S_i| = L$

$\text{query}_j$ は次のどちらかの形式である。

$1\ k\ c\ d$

• $k$ は整数、 $c, d$ は英小文字 $1$ 文字
• $1 \le k \le L$
• $c \ne d$

$2\ t$

• $t$ は英小文字からなる文字列
• $1 \le |t| \le L$

出力

$1$ 行に答えを出力し、最後に改行してください。

$K$ 行出力してください。 $K$ はクエリ2の個数です。 $i$ 行目には $i$ 個目のクエリ2に対する答えを出力してください。(22:04 binap 追記)

サンプル

4 3 3
aaa
aba
bbb
ccc
2 aa
1 2 b a
2 aa

1
2

10 4 10        
jgda
urom
fczy
qnkk
byvw
mjgi
xuru
ifcg
tqns
ebye
1 2 q j
2 fc
1 4 m k
2 tj
2 t
2 qnk
1 3 v y
2 j
2 ebye
2 eby

1
1
1
1
1
1
1

12 6 20
hyllru
hyalzk
hysuka
hetwxb
hetwxb
hysuka
hysuka
hytebn
hetgxn
hetekv
wqmhgk
hywdtu
2 hywdt
2 wqmhgk
1 1 w h
1 6 k n
2 hetgx
1 2 e y
2 h
2 hyalz
1 4 g w
2 h
2 hytekv
2 h
2 h
1 5 x k
2 hyt
1 4 u e
1 2 y q
2 hqllru
2 hqalz
1 5 z t

1
1
1
12
1
12
1
12
12
5
1
1