#6806. String

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

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

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

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

• 如果读入的是 1 c 表示在字符串的末尾添加一个字符，这个字符的 ASCII 码应当等于

  $$(c - \text{'a'} + \text{tmp}) \bmod 26 + \text{'a'} $$

• 如果读入的是 2 l r 表示选择 $S$ 从第

  $$(l - 1 + \text{tmp}) \bmod \text{len} + 1$$

  位到

  $$(r - 1 + \text{tmp}) \bmod \text{len} + 1$$

  位（$\text{len}$ 代表当前 $S$ 的长度）的部分作为子串 $T$，询问 $T$ 中最长的至少出现两次的子串长度，同时你应当把 $\text{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

说明

• 操作类型 $1$ 是在末尾添加字符，但字符会受上一次询问结果 $\text{tmp}$ 影响。
• 操作类型 $2$ 是询问子串 $T$ 中最长的至少出现两次的子串长度，并且查询的区间 $l, r$ 也会受 $\text{tmp}$ 影响。
• 初始 $\text{tmp} = 0$。