题目描述

给定一个初始字符串，支持三种操作：

1. 查询：计算两个后缀的公共前缀长度 $\text{LCQ}(x, y)$
2. 修改：将字符串中第 $x$ 个字符改为 $d$
3. 插入：在第 $x$ 个字符后插入字符 $d$（$x=0$ 表示开头插入）

输入格式

• 第一行：初始字符串
• 第二行：操作数 $M$
• 接下来 $M$ 行：操作指令
  • Q x y：计算 $\text{LCQ}(x,y)$
  • R x d：修改第 $x$ 个字符为 $d$
  • I x d：在第 $x$ 个字符后插入 $d$

输出格式

对每个查询输出一行答案

样例

输入

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 \leq 150000$
• 字符串长度 $L \leq 10^5$
• 查询操作不超过 $10000$ 个
• 字符串仅包含小写字母