题目描述

为了给 Wind 买生日礼物，Jiajia 不得不找了一份检查文本的工作。这份工作很无聊：给你一段文本，要求比对从文本中某两个位置开始能匹配的最大长度是多少。但比无聊更糟糕的是，Jiajia 的经理还可能往文本里面插入一些字符。

Jiajia 想用一个程序来解决这些繁琐的工作。这个程序的速度要足够快，因为 Wind 的生日就快要到了，Jiajia 必须赚到足够多的钱，也就是处理足够多的文本。

输入格式

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

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

I ch p：表示将一个字符 $ch$ 插入到当前文本的第 $p$ 个字符之前，如果 $p$ 大于当前文本长度则表示插入到当前文本末尾；

Q i j：表示询问当前文本从原始文本的第 $i$ 个和第 $j$ 个字符现在所在的位置开始能匹配的字符是多少。

输出格式

对于每条 $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$ 条。