题目描述
维护一个小写字母的字符串vector $S$，支持操作：
- I k s 在第 $k$ 个位置后插入串 $s$（若 $k = 0$ 则插入到序列的开头）。
- Q l r s 查询串 $s$ 在位置 $[l, r]$ 中的多少个串中出现过。 部分数据强制在线。
输入格式
从标准输入读入数据。
输入共 $M + 1$ 行。
第一行两个非负整数 M, T，表示操作次数及是否需要强制在线。
接下来 M 行，每行表示一个操作，格式如题目描述所示。
为了强制在线，当 $T = 1$ 时，若输入的整数为 $a$，则真实的输入数据为a xor lastans。输入的字符串由小写字母构成，若输入的小写字母在字母表中是第 $b$ 个，真实的小写字母在字母表中是第 $(b + lastans) \bmod 26 + 1$ 个。其中$lastans$ 表示上一次询问的答案，初始 $lastans = 0$。
输出格式
输出到标准输出。
对于每个 $Q$ 操作，输出一行表示答案。
样例
输入
5 0
I 0 orzfsf
I 1 fsforz
Q 1 2 fsf
I 0 orz
Q 1 3 orz输出
2
3子任务
令 $L_M$ 为修改串的总长度，$L_Q$ 为询问串的总长度。
对于所有数据，$1 \le M \le M_{max}, 1 \le L_M \le 3M, 1 \le L_Q \le 2M$，解密后 $k$, $l$, $r$ 的值均保证合法。
对于测试点 $1$，在所有 I 操作都进行完后才会出现 Q 操作。
| 测试点编号 | $T$ | $M_{max}$ | 此部分分值 | 时限 |
|---|---|---|---|---|
| 1 | 0 | $40000$ | $10$ | $4S$ |
| 2 | 0 | $40000$ | $20$ | $4S$ |
| 3 | 1 | $40000$ | $20$ | $4S$ |
| 4 | 1 | $40000$ | $20$ | $4S$ |
| 5 | 1 | $100000$ | $30$ | $9S$ |
空间限制：$1024\texttt{MB}$
