Description

背景
黑暗魔君复活，魔戒重现，这一切的一切都意味这黑暗即将重新笼罩中土大陆，为了避免人类被邪恶的黑魔法生物奴隶直至灭绝的命运，甘道夫带领的魔戒远征队背负着第三纪元以来最沉重的使命，出发末日火山前往销毁黑暗魔君的戒指之王，然而，他们意外掉进了精灵的陷阱，企图逃出的时候却发现要离开此地要回答一系列鬼畜至极的问题……
描述
石壁上用精灵最古老的语言刻着几行大字（这怎么难得倒语言专家甘道夫呢~）：愚蠢的生物们，竟敢轻易扰乱高贵的西方精灵居住过的圣地，你们就要为此付出代价！看着古老的圣言，按下石壁上的开关，我们会告诉你们一段最优美的文字组成的语言，然后我们会对你们以提问的形式进行考验，每个提问我们会给你一段用同种文字组成的话语，然后你必须回答我们给出的语言会引发我们最初给出那段语言里面多少个不同的连续片段（相当于字符串中的子串）的共鸣！当然，这是不会这么简单的，我们还有有时候在该最初给出的语言前面添加一个字母，然后这个修改操作对于之后的所有修改操作和提问有效。（吐槽：精灵的语言实在是太优雅了，计算姬根本就表达不出来，所以只能用’a’…’z’勉强代替了，嗯）（对于语言共鸣现象，我们假如把语言表示成两个串s0,s1，假如s0是s1的一个前缀，那么s0可以引发s1的共鸣，注意，这里共鸣是单向的，即s0可以引发s1的共鸣，但是s1可能无法引发s0的共鸣）正当已经放弃治疗的甘道夫正准备按下开关的时候，突然在开关下面看到了一行用火星文写的小字：
啦啦啦~~~这么水的题写了怎么会过瘾呢真是的，所以我就顺手改了一下系统，所有的修改操作现在都进行了加密，对于每个修改操作，假如添加的字母是’a’…’z’中的第c个（从0开始编号）,那么真实操作的字母其实是第（c +key*lastans）%26个字母，lastans表示最近一次提问的答案，初始时为0，%表示取模运算符，相当于pascal语言中的mod。
                                 ——KPM到此一游~~~

Input

输入第一行包括一个字符串s，该串表示初始给出的语言
第二行包括两个整数key m ，key意义如题面所示，m表示操作与提问的总个数有m个
接下来m行，如果第一个数字是0，表示这是一个提问，如果是1表示这是一个修改操作：
如果是提问：接下来包括一个串si,表示查询所提供该段语言
如果是修改操作：接下来给出一个字符ci，对于如题面解密之后得到的字符ci’，将其加在字符串s的头部。

Output

对于每个提问，输出相应的答案。

Sample Input

Sample Output

Hint

样例解释

第一个操作，查询”ababc”中以”ab”为前缀的不同的子串的个数，总共有:”ab”、“aba”、”abc”、”abab”、”ababc”5个；

第二个操作，在字符串”ababc”前面添加一个字符’a’,变成”aababc”;

第三个操作，查询”aababc”中以”a”为前缀的不同子串的个数，总共有:”a”、”aa”、“ab”、”aab”、”aba”、”abc”、

”aaba”、”abab”、”aabab”、”ababc”、“aababc”11个。

数据范围与约定

对于10%的数据，保证0<m,len(s)<=100,0< <=1000

对于另外40%的数据，保证0<m,len(s)<=50000,0<<=500000,key=0

对于另外50%的数据，保证0<m,len(s)<=50000,0<<=500000,key>0

对于100%的数据，key<=10。

Source