#4963. String

内存限制:512 MiB 时间限制:20 Sec

题目描述

给定一个字符串S,它的下标从1开始。需要支持两种操作:
1 c在S最后插入一个字符c。
2 l r询问由S的第l位到第r位构成的字符串中,出现次数大于等于两次的字符串的长度的最大值。
我们会通过某些方法使你必须在线的支持操作。

输入格式

第一行一个字符串,表示S。
第二行一个数m,表示操作次数。
接下来m行,每行表示一次操作。每种操作形如1 c或者2 l r。
设上次答案为lastans,当前字符串的长度为len。
如果为1c,那么真正插入的字符为(c-'a'+lastans)mod 26+'a'。
如果为2 l r,那么令l'=((l-1+lastans) mod len)+1
r'=((r-1+lastans) mod len)+1。
如果此时l'>r',则交换l'和r'。真正的询问区间即为l'到r'。
设字符串初始长度为N,N,M<=50000,保证S中只有小写字符,1<=L,R<=Len

输出格式

对于每个询问操作,输出一行一个数,表示答案。如果不存在一个满足条件的串,则输出0。

样例

样例输入


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

样例输出


			
1
2
3
2

数据范围与提示