配点 : 100 点
問題文
非空字符串 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 是一个小写字母 表示第
入力
输入将以以下格式从标准输入给出。
N
S
T
Q
\mathrm{Query}_{1}
\mathrm{Query}_{2}
\vdots
\mathrm{Query}_{Q}
但是, 运算前设定中包含的\mathrm{Query}_{i} 是 i 个查询的内容。每个查询的内容按以下格式给出:
- i 第一个查询是查询 1 什么时候
1 L R
- i 第一个查询是查询 2 什么时候
2 X Y C
出力
每个查询 回答 1 请在 1 行输出。 它应该打印
入力例 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