要求在线询问一个串在原串中出现的次数，并且可以在原串末尾添加字符串
如果没有修改的话，考虑建出(parent)树之后统计每个(endpos)节点的(right)集合大小，现在要求动态添加字符，那么由于(parent)树的形态会变，所以用(LCT)来维护(parent)树，具体就是增删(link)边
(LCT)一直以初始状态为根，每次提出来初始状态到当前节点的链然后更新一条链上的值即可，根一直没变，不需要(makeroot)操作也不需要(split)操作，直接(access)当前点，然后(splay)上去之后更新
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int MAXN = (6e5+7)*2;
void decode(string& str, int mask){
for(int i = 0; i < (int)str.size(); i++){
mask = (mask*131+i)%str.size();
swap(str[i],str[mask]);
}
}
struct LinkCutTree{
int ch[MAXN][2],fa[MAXN],val[MAXN],lazy[MAXN],rev[MAXN];
bool isroot(int rt){ return ch[fa[rt]][0]!=rt and ch[fa[rt]][1]!=rt; }
int check(int rt){ return rt == ch[fa[rt]][1]; }
void pushdown(int rt){
if(rev[rt]){
swap(ch[rt][0],ch[rt][1]);
rev[ch[rt][0]] ^= 1;
rev[ch[rt][1]] ^= 1;
rev[rt] ^= 1;
}
if(lazy[rt]){
if(ch[rt][0]){
val[ch[rt][0]] += lazy[rt];
lazy[ch[rt][0]] += lazy[rt];
}
if(ch[rt][1]){
val[ch[rt][1]] += lazy[rt];
lazy[ch[rt][1]] += lazy[rt];
}
lazy[rt] = 0;
}
}
void pushdownall(int rt){
if(!isroot(rt)) pushdownall(fa[rt]);
pushdown(rt);
}
void rotate(int rt){
int f = fa[rt], gf = fa[f], d = check(rt);
if(!isroot(f)) ch[gf][check(f)] = rt;
fa[rt] = gf;
ch[f][d] = ch[rt][d^1]; fa[ch[rt][d^1]] = f;
ch[rt][d^1] = f; fa[f] = rt;
}
void splay(int rt){
pushdownall(rt);
while(!isroot(rt)){
int f = fa[rt];
if(!isroot(f)){
if(check(rt)==check(f)) rotate(f);
else rotate(rt);
}
rotate(rt);
}
}
void access(int rt){
int c = 0;
while(rt){
splay(rt);
ch[rt][1] = c;
rt = fa[c = rt];
}
}
void link(int x, int f){
fa[x] = f; access(f); splay(f);
val[f] += val[x]; lazy[f] += val[x];
}
void cut(int u){
access(u);
splay(u);
lazy[ch[u][0]] -= val[u];
val[ch[u][0]] -= val[u];
fa[ch[u][0]] = 0; ch[u][0] = 0;
}
int query(int u){
splay(u);
return val[u];
}
}lct;
struct SAM{
int len[MAXN],link[MAXN],ch[MAXN][26],tot,last;
SAM(){ link[last = tot = 1] = 0; }
void extend(int c){
int np = ++tot, p = last;
lct.val[np] = 1;
len[np] = len[last] + 1;
while(p and !ch[p][c]){
ch[p][c] = np;
p = link[p];
}
if(!p){
link[np] = 1;
lct.link(np,1);
}
else{
int q = ch[p][c];
if(len[p]+1==len[q]){
link[np] = q;
lct.link(np,q);
}
else{
int clone = ++tot;
len[clone] = len[p] + 1;
link[clone] = link[q];
lct.link(clone,link[q]);
for(int i = 0; i < 26; i++) ch[clone][i] = ch[q][i];
lct.cut(q); lct.link(q,clone);
lct.link(np,clone);
link[np] = link[q] = clone;
while(p and ch[p][c]==q){
ch[p][c] = clone;
p = link[p];
}
}
}
last = np;
}
int calsub(string s){
int u = 1;
for(int i = 0; i < (int)s.size(); i++){
int c = s[i] - 'A';
if(!ch[u][c]) return 0;
u = ch[u][c];
}
return lct.query(u);
}
}sam;
int n,mask;
string s,op;
int main(){
//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> s;
for(int i = 0; i < (int)s.size(); i++) sam.extend(s[i]-'A');
while(n--){
cin >> op >> s;
decode(s,mask);
if(op[0]=='Q'){
int ret = sam.calsub(s);
mask ^= ret;
cout << ret << endl;
}
else for(int i = 0; i < (int)s.size(); i++) sam.extend(s[i]-'A');
}
return 0;
}