每次是将 $1$ 到根的路径上加 $1$。

#include<bits/stdc++.h>

using namespace std;

inline int read(){
	int x=0,f=0;
	char c=getchar();
	while(c<'0'||c>'9'){f|=(c=='-');c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return f?-x:x;
}

const int Max=2e6+10;
struct LCT{
	struct node{
		int ch[2],val,tag,add,fa;
		#define ch(k,i) tr[k].ch[i]
		#define tag(k) tr[k].tag
		#define add(k) tr[k].add
		#define val(k) tr[k].val
		#define fa(k) tr[k].fa
	}tr[Max];
	inline bool chk(int k){return k==ch(fa(k),1);}
	inline bool isroot(int k){return (k!=ch(fa(k),0))&&(k!=ch(fa(k),1));}
	void Add(int x,int v){
		add(x)+=v;
		val(x)+=v; 
	}
	void rever(int x){
		swap(ch(x,0),ch(x,1));
		tag(x)^=1;
	}
	void pushdown(int x){
		if(tag(x)){
			rever(ch(x,0));
			rever(ch(x,1));
			tag(x)=0;
		}
		if(add(x)){
			Add(ch(x,0),add(x));
			Add(ch(x,1),add(x));
			add(x)=0;
		}
	}
	void Alldown(int x){
		if(!isroot(x)) Alldown(fa(x));
		pushdown(x);
	}
	void rotate(int x){
		int y=fa(x),z=fa(y),fg=chk(x);
		int w=ch(x,!fg);
		ch(y,fg)=w;ch(x,!fg)=y;
		if(!isroot(y)) ch(z,chk(y))=x;
		fa(x)=z;fa(w)=y;fa(y)=x;
	}
	void splay(int x){
		Alldown(x);
		while(!isroot(x)){
			int y=fa(x);
			if(!isroot(y)) rotate((chk(x)^chk(y))?x:y);
			rotate(x);
		}
	}
	void access(int x){
		for(int y=0;y;x=fa(y=x))
			splay(x),ch(x,1)=y;
	}
	void makeroot(int x){access(x);splay(x);rever(x);}
	int findroot(int x){
		access(x);splay(x);
		while(ch(x,0)) pushdown(x),x=ch(x,0);
		splay(x);return x;
	}
	void split(int x,int y){makeroot(x);access(y);splay(y);}
	void cut(int x,int y){split(x,y);ch(y,0)=fa(x)=0;}
	void link(int x,int y){makeroot(x);fa(x)=y;}
	int query(int x){split(1,x);return val(x);}
	void update(int x,int v){split(1,x);Add(x,v);}
	#undef fa
	#undef ch
}t;

struct SAM{
	struct Node{
		int ch[27],fa,len;
		#define ch(k,i) Tr[k].ch[i]
		#define len(k) Tr[k].len
		#define fa(k) Tr[k].fa
	}Tr[Max];
	int tot,p,now,to;
	SAM(){tot=now=1;}
	void insert(int x){
		p=now;len(now=++tot)=len(p)+1;
		for(;p&&!ch(p,x);p=fa(p)) ch(p,x)=now;
		if(!p) fa(now)=1;
		else {
			to=ch(p,x);
			if(len(p)+1==len(to)) fa(now)=to;
			else {
				Tr[++tot]=Tr[to];
				t.val(tot)=t.query(to);
				len(tot)=len(p)+1;
				int su=t.query(to);
				t.cut(fa(to),to);
				t.update(fa(to),-su);
				t.link(fa(to),tot);
				t.link(to,tot);
				t.update(tot,su);
				fa(to)=fa(now)=tot;
				for(;p&&ch(p,x)==to;p=fa(p)) ch(p,x)=tot;
			} 
		}
		t.link(fa(now),now);
		t.update(now,1);
	}
	int ask(char *s){
		int n=strlen(s),now=1,to=0;
		for(int i=0;i<n;++i){
			to=s[i]-'A';
			if(!ch(now,to)) return 0;
			now=ch(now,to);
		}
		return t.query(now);
	}
	#undef fa
	#undef ch
}s;
int n,mask,m;
char in[Max],opt[15];

void decode(char *in,int mask){
	int len=strlen(in);
	for(int i=0;i<len;++i){
		mask=(mask*131+i)%len;
		swap(in[i],in[mask]);
	}
}

int main(){
	m=read();
	scanf("%s",in);
	n=strlen(in);
	for(int i=0;i<n;++i) s.insert(in[i]-'A');
	for(int i=1;i<=m;++i){
		scanf("%s",opt);
		scanf("%s",in);
		decode(in,mask);
		if(opt[0]=='A') {
			n=strlen(in);
			for(int i=0;i<n;++i) s.insert(in[i]-'A');
		}else {
			int res=s.ask(in);
			mask^=res;
			printf("%d\n",res);
		}
	}
	return 0;
}