$N$ 人の人が左から右へ一列に並んでいる。彼らの間では文字列 $S$ が流行している。
各人は、以下の条件を満たすとき幸せであり、そうでないとき幸せではない。
以下の $2$ 種類のクエリを合計 $Q$ 回処理せよ。
クエリ1
$1$ $l$ $r$ $c$
区間 $[l, r]$ に含まれる人に文字列 $c$ を左から一文字ずつ伝える。
クエリ2
$2$ $l$ $r$
区間 $[l, r]$ に含まれる幸せな人の数を求める。
ただし、区間 $[l, r]$ とは、左から $l$ 番目から $r$ 番目までの人のことを表す。
入力は以下の形式で与えられる。
$S$ $N$ $Q$ $query_1$ $\vdots$ $query_Q$
$1$ 行目に流行している文字列 $S$ が与えられる。
$2$ 行目に並んでいる人の数 $N$ とクエリの数 $Q$ が空白区切りで与えられる。
$3$ 行目から続く $Q$ 行にクエリの情報が与えられる。
入力は以下の条件を満たす。
各クエリ2について、幸せな人の数を1行に出力せよ。
abab 5 5 2 2 4 1 1 5 abab 2 3 5 1 3 3 a 2 1 5
0 3 4
uku 1333 5 2 232 423 1 13 532 uku 2 322 567 1 3 33 ku 2 1 333
0 211 321
aabb 1879 20 2 69 1585 1 415 1680 aabb 1 756 1628 abbabbaa 1 849 1273 abba 2 418 1172 2 1063 1164 2 203 623 2 481 1209 1 107 110 ababaaaab 1 857 985 bbbbabbbaa 1 868 947 aaa 1 1619 1789 aabab 2 204 844 2 493 1422 2 821 1499 1 757 1817 abbabbb 2 232 911 1 653 797 aaabaaaab 2 701 1657 1 868 940 aaabbbaaa
0 338 0 209 275 341 263 0 341 0