SAM+LCT维护parent tree版本
虽然说子树维护那套理论需要ETT
不过parent tree的根是固定的，所以用lct加一些奇怪的乱搞就行了
//随手拖个SAM的板子和LCT的板子，然后再加几句话就写完了【手动滑稽
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define N 1200006using namespace std;
struct LinkCutTree{
#define ls(a) (t[a].c[0])
#define rs(a) (t[a].c[1])
struct LCTnode{
int c[2],fa;
int sum,tag;
} t[N];
void newnode(int x,int value){
ls(x)=rs(x)=t[x].fa=t[x].tag=0;
t[x].sum=value;
}
void Add(int x,int delta){
if (!x) return;
t[x].sum+=delta;t[x].tag+=delta;
}
int f(int x){return (ls(t[x].fa)!=x)*(1-2*(rs(t[x].fa)!=x));}
void PushDown(int x){
if (t[x].tag){
Add(ls(x),t[x].tag);
Add(rs(x),t[x].tag);
t[x].tag=0;
}
}
void rotate(int x){
int y=t[x].fa,z=t[y].fa,k=f(x),fz=f(y);
if (fz>=0) t[z].c[fz]=x;
t[y].c[k]=t[x].c[k^1];t[x].c[k^1]=y;
t[t[y].c[k]].fa=y;t[x].fa=z;t[y].fa=x;
}
int stack[N],top;
void splay(int x){
top=0;stack[top++]=x;
for (int i=x;f(i)>=0;i=t[i].fa) stack[top++]=t[i].fa;
while (top) PushDown(stack[--top]);
for (;f(x)>=0;rotate(x))
if (f(t[x].fa)==f(x)) rotate(t[x].fa);
else if (f(t[x].fa)>=0) rotate(x);
}
void access(int x){
for (int son=0;x;son=x,x=t[x].fa)
splay(x),rs(x)=son;
}
void link(int u,int f){
access(f);splay(f);Add(f,t[u].sum);
t[u].fa=f;
}
void cut(int u){
access(u);splay(u);Add(ls(u),-t[u].sum);
ls(u)=t[ls(u)].fa=0;
}
int getsum(int u){
splay(u);return t[u].sum;
}
} pt;struct SAM{
struct SAMnode{
int par,mx,go[26];
SAMnode(){}
SAMnode(int _mx):par(0),mx(_mx){
memset(go,0,sizeof(go));
}
} t[N];
int last,size;
int newnode(int _mx,int value){
t[++size]=SAMnode(_mx);
pt.newnode(size,value);
return size;
}
void clear(){size=0;last=newnode(0,0);}
void extend(char c){
c-='A';
int p=last,np=newnode(t[p].mx+1,1);
for (;p&&!t[p].go[c];p=t[p].par) t[p].go[c]=np;
if (!p) t[np].par=1,pt.link(np,1);
else{
int q=t[p].go[c];
if (t[p].mx+1==t[q].mx) t[np].par=q,pt.link(np,q);
else{
int nq=newnode(t[p].mx+1,0);
memcpy(t[nq].go,t[q].go,sizeof(t[q].go));
t[nq].par=t[q].par;pt.link(nq,t[q].par);
t[np].par=nq;pt.link(np,nq);
pt.cut(q);t[q].par=nq;pt.link(q,nq);
for (;p&&t[p].go[c]==q;p=t[p].par) t[p].go[c]=nq;
}
}
last=np;
}
int solve(char *s){
int p=1;
for (int i=0;p&&s[i];++i) p=t[p].go[s[i]-'A'];
if (!p) return 0;
return pt.getsum(p);
}
} sam;void decode(char *s,int mask){
int l=strlen(s);
for (int i=0;i<l;++i){
mask=(mask*131+i)%l;
swap(s[i],s[mask]);
}
}char st[N],op[10];
int main(){
int Q;scanf("%d%s",&Q,st);
sam.clear();
for (int i=0;st[i];++i) sam.extend(st[i]);
int mask=0,res;
while (Q--){
scanf("%s%s",op,st);
decode(st,mask);
if (op[0]=='Q'){
printf("%d\n",res=sam.solve(st));
mask^=res;
}
else for (int i=0;st[i];++i) sam.extend(st[i]);
}
return 0;
}
