問題文

バス (bus) はオムニバス (omnibus) の略語です。

このように、英小文字からなる長さ $3$ 以上の文字列 $X$ に対して、$X$ の末尾 $3$ 文字を取り出した文字列を $X$ の略語と呼ぶことにします。

$i$ 文字目が文字 $S_i$ である長さ $N$ の文字列 $S$ が与えられます。$Q$ 個のクエリを順に処理してください。

各クエリは次のいずれかのタイプです。

• タイプ $1$ 1 k x : $S_k$ を文字 $x$ に変更する
• タイプ $2$ 2 l r a : $S$ の $l$ 文字目から $r$ 文字目を取り出した文字列を $T$ とする。$T$ の長さ $3$ 以上の(連続)部分文字列で、略語が $a$ と一致するものの個数を出力する

ただし、部分文字列は、文字列として同じでも取り出す位置が異なれば区別します。

入力

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

• $3\leq N\leq 2\times 10^5$
• $1\leq Q\leq 2\times 10^5$
• $S$ は英小文字からなる長さ $N$ の文字列
• $N, Q$ は整数

ここで $query_i (1\leq i\leq Q)$ は $i$ 番目のクエリであり、以下のいずれかの形式です。

$1\ k\ x$

• $k$ は $1\leq k\leq N$ を満たす整数
• $x$ は英小文字

$2\ l\ r\ a$

• $1\leq l\leq r\leq N$
• $a$ は英小文字からなる長さ $3$ の文字列
• $l, r$ は整数

出力

タイプ $2$ のクエリに対する答えを順に出力してください。$k$ 行目には、$k$ 個目のタイプ $2$ のクエリに対する答えを出力してください。ただし、タイプ $2$ のクエリが必ず $1$ つ以上与えられるとは限りません。
最後に改行してください。

サンプル

14 5
ambushbusiness
2 1 5 bus
2 1 12 bus
1 3 x
2 1 12 bus
2 3 10 usi

3
10
7
6