問題文

空でない文字列 X と非負整数 K に対して、\operatorname{rot}(X,K) を次のように定めます。

• X の先頭の文字を末尾に移動させるという操作を K 回行った結果得られる文字列。

長さの等しい空でない文字列 X, Y に対し、f(X, Y) を次のように定めます。

• 0\leq i\lt|X| かつ \operatorname{rot}(X,i) が \operatorname{rot}(Y,i) よりも辞書順で小さくなるような整数 i の個数。

正整数 N と、ともに長さが N である文字列 S,T が与えられます。以下の 2 種類のクエリが合計で Q 個与えられるので処理してください。

• クエリ 1: 整数 L,R が与えられる。S の L 文字目から R 文字目までを抜き出して得られる文字列を S'、T の L 文字目から R 文字目までを抜き出して得られる文字列を T' として、f(S',T') を求める。
• クエリ 2: 整数 X, Y と英小文字 C が与えられる。X = 1 のとき S の Y 文字目を C で置き換える。X = 2 のとき T の Y 文字目を C で置き換える。

制約

• 1\leq N\leq 2\times 10^{5}
• S と T は英小文字からなる長さ N の文字列
• 1\leq Q\leq 2\times 10^{5}
• クエリ 1 について、1\leq L\leq R\leq N
• クエリ 2 について、X\in\lbrace 1,2\rbrace,1\leq Y\leq N であり、C は英小文字

入力例 1

9
dacbyzyzx
dcabzyzyx
6
1 2 4
1 5 9
2 1 1 z
1 1 1
2 2 9 a
1 6 9

出力例 1

2
3
0
1

1 番目のクエリについて説明します。S'=\mathtt{acb},T'=\mathtt{cab} であり、f(S',T') を出力する必要があります。

• \operatorname{rot}(S',0)=\mathtt{acb},\operatorname{rot}(T',0)=\mathtt{cab}
• \operatorname{rot}(S',1)=\mathtt{cba},\operatorname{rot}(T',1)=\mathtt{abc}
• \operatorname{rot}(S',2)=\mathtt{bac},\operatorname{rot}(T',2)=\mathtt{bca}

ですから、このクエリに対する出力は 2 です。

入力例 2

20
pilrajvvuwrcxvbchgyf
pitlabnvzyrmoveahgyr
20
2 2 3 l
2 2 3 l
1 3 17
2 1 6 b
1 1 13
1 19 20
1 8 14
1 2 16
2 1 9 c
2 2 19 x
2 1 20 r
2 2 9 c
1 7 7
1 11 13
1 10 20
1 9 11
2 2 1 b
1 6 16
2 1 1 w
2 1 1 q

出力例 2

7
5
2
6
7
0
2
6
3
7