[AdditionalFile6806.zip](file://AdditionalFile6806.zip?type=additional_file)

#6806. String

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目来自 2016 ACM/ICPC Asia Regional Qingdao Online

Alice 有一个只包含小写字母的字符串 $S$，现在她要对这个字符串进行 $m$ 次操作，每次操作可以是在 $S$ 末端新加入一个字符，或者选择 $S$ 的某个子串 $T$，询问 $T$ 的所有在 $T$ 中至少出现两次的子串中，最长的子串长度是多少。如果 $T$ 没有至少出现两次的子串，则结果应为 $0$。

输入格式

第一行包含一个只包含小写字母的字符串 $S$ 和正整数 $m$，分别表示 Alice 一开始持有的串和操作次数。

以下 $m$ 行每行描述一个操作。为了正确读入所有数据，你需要维护一个变量 tmp 表示最后一次询问的结果，初始值为 $0$。

如果读入的是 1 c 表示在字符串的末尾添加一个字符，这个字符的 ASCII 码应当等于 (c - 'a' + tmp) mod 26 + 'a'。

如果读入的是 2 l r 表示选择 $S$ 从第 (l - 1 + tmp) mod len + 1 位到 (r - 1 + tmp) mod len + 1 位（len 代表当前 $S$ 的长度）的部分作为子串 $T$，询问 $T$ 中最长的至少出现两次的子串长度，同时你应当把 tmp 更新为本次询问的结果。

字符串的初始长度和操作次数都不超过 $5 \times 10 ^4$。

输出格式

对每个询问操作，单独一行输出答案。

样例

输入

aabda 6
2 1 4
1 a
2 1 5
1 b
2 6 5
2 7 4

输出

1
2
3
2

数据范围与提示

数据可能有点弱，如有问题请联系 @AntiLeaf