// bzoj2555

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<ctime>

#define RG register

#define LL long long

#define inf (1ll<<30)

#define MOD 1000000007

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=600010,maxm=3000010;

char s[maxm];

int Q,mask,r[maxn<<1];

namespace LCT {

	int tr[maxn<<1][2],fa[maxn<<1],tag[maxn<<1];

	void pushdown(int x) {

		if (tr[fa[x]][0]==x || tr[fa[x]][1]==x) pushdown(fa[x]);

		if (tag[x]) {

			r[tr[x][0]]+=tag[x];tag[tr[x][0]]+=tag[x];

			r[tr[x][1]]+=tag[x];tag[tr[x][1]]+=tag[x];

			tag[x]=0;

		}

	}

	void rotate(int x) {

		int y=fa[x],z=fa[y],l,r;

		l=tr[y][1]==x;r=l^1;

		if (tr[z][0]==y || tr[z][1]==y) tr[z][tr[z][1]==y]=x;

		fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;

		tr[y][l]=tr[x][r];tr[x][r]=y;

	}

	void splay(int x) {

		pushdown(x);

		while (tr[fa[x]][0]==x || tr[fa[x]][1]==x) {

			int y=fa[x],z=fa[y];

			if (tr[z][0]==y || tr[z][1]==y) {

				if (tr[z][0]==y ^ tr[y][0]==x) rotate(x);

				else rotate(y);

			}

			rotate(x);

		}

	}

	void access(int x) {

		for (int y=0;x;y=x,x=fa[x])

			splay(x),tr[x][1]=y;

	}

	void add(int x,int val) {

		r[x]+=val;tag[x]+=val;

	}

	void link(int x,int y) {

		access(y);splay(y);add(y,r[x]);

		fa[x]=y;

	}

	void cut(int x) {

		access(x);splay(x);add(tr[x][0],-r[x]);

		tr[x][0]=fa[tr[x][0]]=0;

	}

	int query(int x) {

		splay(x);return r[x];

	}

}

using namespace LCT;

namespace SAM {

	int Dargen,last,sz;

	int len[maxn<<1],ch[maxn<<1][26],par[maxn<<1];

	void Init() {Dargen=last=sz=1;}

	void Extend(int c) {

		int np=++sz,p=last;last=np;

		len[np]=len[p]+1;r[np]=1;

		for (;p && !ch[p][c];p=par[p]) ch[p][c]=np;

		if (!p) par[np]=Dargen,link(np,Dargen);

		else {

			int q=ch[p][c];

			if (len[p]+1==len[q]) par[np]=q,link(np,q);

			else {

				int nq=++sz;len[nq]=len[p]+1;

				memcpy(ch[nq],ch[q],sizeof(ch[q]));

				par[nq]=par[q],link(nq,par[q]);

				par[np]=par[q]=nq;

				cut(q),link(np,nq),link(q,nq);

				for (;p && ch[p][c]==q;p=par[p]) ch[p][c]=nq;

			}

		}

	}

	int match(char *r) {

		int p=Dargen,l=strlen(r);

		for (int i=0;i<l;i++) {

			if (!ch[p][r[i]-'A']) return 0;

			p=ch[p][r[i]-'A'];

		}

		return query(p);

	}

}

using namespace SAM;

void decode(char *r,int t) {

	int len=strlen(r);

	for (int j=0;j<len;j++) {

		t=(t*131+j)%len;

		swap(r[j],r[t]);

	}

}

int main() {

	scanf("%d",&Q);

	scanf("%s",s+1);

	Init();

	int n=strlen(s+1);

	for (int i=1;i<=n;i++) Extend(s[i]-'A');

	char ch[10];mask=0;

	while (Q--) {

		scanf("%s%s",ch,s);

		decode(s,mask);

		n=strlen(s);

		if (ch[0]=='A') for (int i=0;i<n;i++) Extend(s[i]-'A');

		if (ch[0]=='Q') {

			int ans=match(s);

			mask^=ans;

			printf("%d\n",ans);

		}

	}

	return 0;

}