[JSOI2008]火星人prefix

火星人最近研究了一种操作：求一个字符串的两个后缀的最长公共前缀。

例如，对于字符串 madamimadam，从左到右将各字符编号为 $1$ 到 $11$：

定义函数 $\operatorname{LCQ}(x,y)$，表示从字符串第 $x$ 个字符开始的后缀与从第 $y$ 个字符开始的后缀的最长公共前缀长度。例如：

$$\operatorname{LCQ}(1,7)=5,\qquad \operatorname{LCQ}(2,10)=1,\qquad \operatorname{LCQ}(4,7)=0。$$

火星人在研究 $\operatorname{LCQ}$ 函数时发现：如果将字符串的所有后缀排序，就可以快速求出 $\operatorname{LCQ}$ 函数的值；反过来，如果能够求出 $\operatorname{LCQ}$ 函数的值，也可以快速将字符串的后缀排序。

尽管火星人找到了快速计算 $\operatorname{LCQ}$ 函数的方法，地球人又提出了一个更困难的问题：在进行询问的同时，还可以修改字符串中的某个字符，或在字符串的某个位置插入一个字符。

你需要维护这个不断变化的字符串，并回答所有 $\operatorname{LCQ}$ 询问。

输入格式

第一行输入初始字符串。

第二行输入一个非负整数 $M$，表示操作数。

接下来 $M$ 行，每行描述一个操作。操作共有以下 $3$ 种：

• Q x y：询问从第 $x$ 个字符开始的后缀与从第 $y$ 个字符开始的后缀的最长公共前缀长度。保证 $1\le x,y\le L$，其中 $L$ 为当前字符串长度；
• R x d：将字符串的第 $x$ 个字符修改为字符 d。保证 $1\le x\le L$；
• I x d：在字符串的第 $x$ 个字符之后插入字符 d。当 $x=0$ 时，在字符串开头插入。保证 $0\le x\le L$。

输出格式

对于每个询问操作，输出对应的答案，每个答案占一行。

样例输入

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

样例输出

5
1
0
2
1

数据范围

• 所有字符串在任意时刻都只由小写英文字母组成；
• $M\le 1.5\times 10^5$；
• 字符串长度 $L$ 在任意时刻都满足 $L\le 10^5$；
• 询问操作的数量不超过 $10^4$；
• 对于第 $1$、$2$ 个测试数据，字符串长度在任意时刻都不超过 $10^3$；
• 对于第 $3$、$4$、$5$ 个测试数据，不包含插入操作。

来源与许可

本题为 JSOI 2008 试题「火星人 prefix」，题面与测试数据整理自 BZOJ。

样例 1

输入

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

输出

5
1
0
2
1