一道套路题。看到“字符串在当前字符串中出现了几次”显然是个SAM的操作。但是有个问题 因为一个点出现次数等于树子树内节点个数，统计一次是的。如何快速求子树和？想到LCT。
那么算法的雏形就有了：在SAM涉及到修改树操作时，利用LCT解决。当SAM上一个点设置为另外一个节点时，需要把自己到祖先这条链（不包含自己），全部加上当前点的子树大小，就是link操作，cut操作同理。
注意查询答案之前需要把查询点的祖先全部的标记下推，所以需要access再splay一下。QAQ
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<set>
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=2*6e5+1000;
struct LCT{
int val[maxn],f[maxn],ch[maxn][2],tag[maxn],stk[maxn];
bool isrt(int u){return (ch[f[u]][0]!=u)&&(ch[f[u]][1]!=u);}
void push_down(int u){
if(!tag[u])return;
val[ch[u][0]]+=tag[u],val[ch[u][1]]+=tag[u];
tag[ch[u][0]]+=tag[u],tag[ch[u][1]]+=tag[u];
tag[u]=0;
}
void rotate(int u){
int x=u,y=f[x],z=f[y],o=ch[y][1]==x,w=ch[x][o^1];
bool flag=isrt(y);
// cout<<">>"<<x<<' '<<y<<' '<<z<<' '<<o<<' '<<w<<' '<<flag<<endl;
ch[y][o]=w;
f[w]=y;
ch[x][o^1]=y;
f[y]=x;
if(!flag)ch[z][ch[z][1]==y]=x;
f[x]=z;
}
void splay(int u){
int top=0;
//cout<<endl<<">> : ";
for(int y=u;;y=f[y]){
//cout<<y<<' '<<f[y]<<' '<<isrt(y)<<endl;
stk[++top]=y;if(isrt(y))break;
}
while(top)push_down(stk[top--]);
for(;!isrt(u);rotate(u)){
int y=f[u];
if(isrt(y))continue;
rotate(((ch[f[u]][0]==u)==(ch[f[y]][0]==y))?y:u);
}
}
void access(int x){
for(int y=0;x;y=x,x=f[x]){
splay(x);ch[x][1]=y;
}
}
void add(int x,int w){val[x]+=w,tag[x]+=w;}
void link(int u,int fa){
access(u);
splay(u);
f[u]=fa;
access(fa);
splay(fa);
add(fa,val[u]);
}
void cut(int u){
access(u);splay(u);add(ch[u][0],-val[u]);
f[ch[u][0]]=0;
ch[u][0]=0;
}
}t;
struct SAM{
int ch[maxn][2],len[maxn],link[maxn],cnt,last;
SAM(){cnt=last=1;}
void insert(int c){
int p=last,cur=++cnt;len[cur]=len[p]+1;t.val[cur]=1;
while(p&&!ch[p][c])
ch[p][c]=cur,p=link[p];
if(!p)link[cur]=1,t.link(cur,1);
else{
int q=ch[p][c];
if(len[p]+1==len[q])link[cur]=q,t.link(cur,q);
else{
int cl=++cnt;len[cl]=len[p]+1;
memcpy(ch[cl],ch[q],sizeof(ch[cl]));
t.cut(q);
t.link(cl,link[q]);link[cl]=link[q];t.link(q,cl);t.link(cur,cl);link[q]=link[cur]=cl;
while(p&&ch[p][c]==q)ch[p][c]=cl,p=link[p];
}
}
last=cur;
}
}sam;
string decodeWithMask(string s, int mask) {
//char[] chars = s.toCharArray();
int lim=s.length();
// for (int j = 0; j < chars.length; j++) {
for (int j = 0; j < lim ; j++){
mask = (mask * 131 + j) % lim;
char t = s[j];
s[j] = s[mask];
s[mask] = t;
}
return s;
}
string s,init,ty;
int main(){
// freopen("in","r",stdin);
ios::sync_with_stdio(0);
int mask=0;int q;cin>>q;
cin>>init;int l1=init.length();
rep(i,0,l1-1)
sam.insert(init[i]-'A');
rep(i,1,q){
cin>>ty>>s;s=decodeWithMask(s,mask);
int l2=s.length();
if(ty[0]=='A'){
rep(j,0,l2-1)sam.insert(s[j]-'A');
}
else{
int u=1;bool flag=0;
rep(j,0,l2-1){
int c=s[j]-'A';
if(!sam.ch[u][c]){cout<<"0"<<endl;mask^=0;flag=1;break;}
else u=sam.ch[u][c];
}
if(flag)continue;
t.access(u);t.splay(u);
ll ans=t.val[u];mask^=ans;
cout<<ans<<endl;
}
}
return 0;
}