Dynamic String(Point Set)

2 secs 1024 MB
Tonegawac's icon Tonegawac

Dynamic String(Point Set)

問題文

英小文字からなる長さ NN の文字列 SS と長さ MM の文字列 TT が与えられます.

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

  • 11 kk cc : SSkk 文字目を cc に変更する
  • 22 l1l_1 l2l_2: SSl1l_1 文字目以降と TTl2l_2 文字目以降のLCP(最長共通接頭辞)の長さを求めて出力する

制約

  • 1N,M,Q5×1051 \leq N, M, Q \leq 5 × 10^5
  • 1k,l1N1 \leq k, l1 \leq N
  • 1l2M1 \leq l2 \leq M
  • cc は英小文字

入力

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

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

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

1 k c 
2 l1 l2 

出力

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

サンプル

入力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
出力1
0
3
1
1
0
0
0

提出


Go (1.21)