Dynamic String(Point Set)

問題文

英小文字からなる長さ $N$ の文字列 $S$ と長さ $M$ の文字列 $T$ が与えられます.

以下の形式で与えられるクエリを $Q$ 回行ってください.

• $1$ $k$ $c$ : $S$ の $k$ 文字目を $c$ に変更する
• $2$ $l_1$ $l_2$: $S$ の $l_1$ 文字目以降と $T$ の $l_2$ 文字目以降のLCP(最長共通接頭辞)の長さを求めて出力する

制約

• $1 \leq N, M, Q \leq 5 × 10^5$
• $1 \leq k, l1 \leq N$
• $1 \leq l2 \leq M$
• $c$ は英小文字

入力

$c$ 以外の入力はすべて整数である.

N M
S
T
Q
query1
query2
query3
.
.
.
queryQ

各クエリは以下のいずれかの形式で入力される

1 k c 

２ l1 l2 

出力

タイプ2のクエリに対する答えを1行ずつ改行して出力してください.

サンプル

18 14
bbbabbbbababbbbbaa
bbbabbbabbbbaa
12
1 7 b
2 9 11
2 13 5
2 18 13
2 10 1
1 4 b
1 7 c
1 17 a
2 17 5
2 7 11
2 11 10
1 17 b

0
3
1
1
0
0
0