pku2758 Checking the Text 文本校对

为了给 Wind 买生日礼物，Jiajia 不得不找了一份检查文本的工作。这份工作很无聊：给定一段文本，需要比较从文本中两个位置开始的字符串，求它们能够匹配的最大长度。更糟糕的是，Jiajia 的经理还可能向文本中插入字符。

Jiajia 希望编写一个程序来处理这些工作。由于 Wind 的生日即将到来，Jiajia 必须尽可能快地处理足够多的文本。

时间限制：$12000\ \mathrm{ms}$。
内存限制：$262144\ \mathrm{KB}$。

输入格式

输入文件第一行是原始文本。

输入文件第二行是操作数 $n$。接下来 $n$ 行，每行描述一条命令。命令有以下两种形式：

• I ch p：将字符 ch 插入到当前文本的第 $p$ 个字符之前。如果 $p$ 大于当前文本长度，则将字符插入到当前文本末尾；
• Q i j：询问当前文本中原始文本第 $i$ 个字符和第 $j$ 个字符当前所在的位置，从这两个位置开始的字符串能够匹配的最长长度。

可以认为，文本初始长度不超过 $5\times 10^4$，I 命令最多有 $200$ 条，Q 命令最多有 $2\times 10^4$ 条。

输出格式

对于每条 Q 命令，输出一行，表示最长匹配长度。

样例输入

abaab
5
Q 1 2
Q 1 3
I a 2
Q 1 2
Q 1 3

样例输出

0
1
0
3

数据范围

• 文本初始长度不超过 $5\times 10^4$；
• I 命令最多有 $200$ 条；
• Q 命令最多有 $2\times 10^4$ 条。

来源与许可

本题题面与测试数据整理自 BZOJ 2258。

样例 1

输入

abaab
5
Q 1 2
Q 1 3
I a 2
Q 1 2
Q 1 3

输出

0
1
0
3