题目描述

$Wind$的生日快到了。为了给她买一份非常非常棒的礼物，$Jiajia$不得不接受一份无聊但赚钱的工作——文本校对员。

这份工作非常单调。$Jiajia$会得到一个由英文字母组成的初始文本字符串，他需要计算从文本的两个不同位置同时开始从左到右逐字符匹配的最大匹配长度。

更糟糕的是，老板有时会在文本的前面、后面或中间插入一些字符。$Jiajia$想写一个程序来自动完成这项工作，这个程序必须足够快，因为距离$Wind$的生日只剩几天了。

输入

输入文件的第一行包含初始文本。
第二行包含命令的数量$n$。接下来的$n$行描述每个命令。命令有两种格式：

1. $I$ $ch$ $p$：在文本的第$p$个字符前插入字符$ch$。如果$p$大于当前文本长度，则在文本末尾插入。
2. $Q$ $i$ $j$：询问从初始文本（不包含插入的字符）的第$i$个和第$j$个字符开始的最大匹配长度。

可以假设初始文本的长度不超过$50000$，$I$命令的数量不超过$200$，$Q$命令的数量不超过$20000$。

输出

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

样例输入

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

样例输出

0  
1  
0  
3  

来源

POJ Monthly--2006.02.26, zgl & twb