Problem J: Ukunichia Query

Problem

$N$ 人の人が左から右へ一列に並んでいる。彼らの間では文字列 $S$ が流行している。
各人は、以下の条件を満たすとき幸せであり、そうでないとき幸せではない。

• 今までに $|S|$ 文字以上の文字を伝えられていて、かつ直近の $|S|$ 文字を古い順から新しい順に並べると $S$ と一致する

以下の $2$ 種類のクエリを合計 $Q$ 回処理せよ。

クエリ1
$1$ $l$ $r$ $c$
区間 $[l, r]$ に含まれる人に文字列 $c$ を左から一文字ずつ伝える。

クエリ2
$2$ $l$ $r$
区間 $[l, r]$ に含まれる幸せな人の数を求める。

ただし、区間 $[l, r]$ とは、左から $l$ 番目から $r$ 番目までの人のことを表す。

Input

入力は以下の形式で与えられる。

$S$
$N$ $Q$
$query_1$
$\vdots$
$query_Q$

$1$ 行目に流行している文字列 $S$ が与えられる。
$2$ 行目に並んでいる人の数 $N$ とクエリの数 $Q$ が空白区切りで与えられる。
$3$ 行目から続く $Q$ 行にクエリの情報が与えられる。

Constraints

入力は以下の条件を満たす。

• $1 \leq |S| \leq 20 $
• $1 \leq N \leq 10^5 $
• $1 \leq Q \leq 10^5 $
• $1 \leq l \leq r \leq N$
• $1 \leq |c| \leq 10 $
• $S, c$ は英小文字からなる
• 各クエリはクエリ1かクエリ2のいずれかである
• クエリ2が必ず一つ以上含まれる

Output

各クエリ2について、幸せな人の数を1行に出力せよ。

Sample Input 1

abab
5 5
2 2 4
1 1 5 abab
2 3 5
1 3 3 a
2 1 5

Sample Output 1

0
3
4

Sample Input 2

uku
1333 5
2 232 423
1 13 532 uku
2 322 567
1 3 33 ku
2 1 333

Sample Output 2

0
211
321

Sample Input 3

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

Sample Output 3

0
338
0
209
275
341
263
0
341
0