火星人是一种好奇心很大的生物。最近，火星人对字符串产生了浓厚的兴趣。他们研究了字符串的LCP： 对于字符串str[1..n]，LCP(i, j)为str[i..n]与str[j..n]这两个字符串的公共前缀长。 例如str="madamimadam"： [IMG]ProblemImg/1823.jpg[/IMG] 有LCP(1, 7) = LCP("madamimadam", "madam") = 5 LCP(4, 8) = LCP("amimadam", "adam") = 1 LCP(10,11) = LCP("am", "m") = 0 后来，火星人发现，如果进行了后缀排序，就能够很快地求LCP，同样，如果能很快地求出字符串的LCP，也可以高效地把所有后缀排序。不过事情总不是想象的那么简单，地球人JS总是喜欢测试火星人的智商：他会在火星人把字符串的后缀排序以后，修改原来的字符串，导致火星人的工作全盘浪费。 于是火星人请到了聪明的你，设计一个程序，对给出的字符串能够支持以下三种操作： 1、求LCP(i, j) 2、将第i个位置的字符修改 3、在第i个位置后插入一个字符 火星人很害怕被地球人耻笑，所以希望你的算法能有很高的执行效率。

输入文件第一行为一个字符串（仅包含小写字母）。 接下来的一行的整数Q代表操作的个数（1 ≤Q ≤150000）。 接下来Q行表示了待执行的操作。 Q i j表示求LCP(i, j)的数值 R i char表示将第i位置的字符替换成小写字母char I i char表示在第i个字符后插入小写字母char

对于每一个Q i j，输出一行为LCP(i, j)的数值。

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