本人已经快疯了，de 了一天半了基本上与 oi-wiki 上长的一模一样了

// 20pts
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

namespace Scapegoat_tree {
    const double A=0.75,INF=1e18;

    struct Node {
        int val,sizt,ch[2];
        double tag;
    }t[2000001];

    int rt,luc,lur[2000001];
    char s[2000001];

    void upd(int x) { if (x) t[x].sizt=t[t[x].ch[0]].sizt+t[t[x].ch[1]].sizt+1; }

	void clear(int x) { t[x].val=t[x].sizt=t[x].ch[0]=t[x].ch[1]=t[x].tag=0; }

    bool ifrbu(int x) { return t[x].sizt*A<(double)std::max(t[t[x].ch[0]].sizt,t[t[x].ch[1]].sizt); }

    bool cmp(int x,int y) { return (s[x]!=s[y]?s[x]<s[y]:t[x-1].tag<t[y-1].tag); }

    void rbuflatten(int x) {
        if (!x) return;
        rbuflatten(t[x].ch[0]);
        lur[++luc]=x;
        rbuflatten(t[x].ch[1]);
//        t[x].ch[0]=t[x].ch[1]=0;
    }

    int rbubuild(int l,int r,double dl,double dr) {
        if (l>=r) return 0;
        int mid=(l+r>>1);double dm=(dl+dr)/2;
        t[lur[mid]].ch[0]=rbubuild(l,mid,dl,dm);
        t[lur[mid]].ch[1]=rbubuild(mid+1,r,dm,dr);
        t[lur[mid]].tag=dm;
        upd(lur[mid]);
        return lur[mid];
    }

    void rbu(int &x,double dl,double dr) { luc=0,rbuflatten(x),x=rbubuild(1,luc+1,dl,dr); }

    void ins(int &x,int k,double dl,double dr) {
        if (!x) {
        	x=k; 
            t[x].tag=(dl+dr)/2,t[x].ch[0]=t[x].ch[1]=0,t[x].sizt=1;
            upd(x);
        } else {
        	double dm=(dl+dr)/2; 
            if (cmp(k,x)) ins(t[x].ch[0],k,dl,dm);
            else ins(t[x].ch[1],k,dm,dr);
            upd(x);
            if (ifrbu(x)) rbu(x,dl,dr);
        }
        return;
    }

    void del(int &x,int k,double dl,double dr) {
        if (!x) return;
        if (x==k) {
            if (!t[x].ch[0] or !t[x].ch[1]) {
            	int tmp=x;x=(t[x].ch[0]|t[x].ch[1]);
//            	clear(tmp);
            	upd(x);
           		if (ifrbu(x)) rbu(x,dl,dr);
            } else {
                int y=t[x].ch[0],f=x;
                while (t[y].ch[1]) {
                    f=y;
                    t[f].sizt--;
                    y=t[y].ch[1];
                }
                if (f==x) t[y].ch[1]=t[x].ch[1];
                else {
                    t[y].ch[0]=t[x].ch[0];
                    t[y].ch[1]=t[x].ch[1];
                    t[f].ch[1]=0;
                }
//                clear(x);
                x=y;
				t[x].tag=(dl+dr)/2;
				upd(x);
           		if (ifrbu(x)) rbu(x,dl,dr);
            }
        } else {
            double dm=(dl+dr)/2;
            if (cmp(k,x)) del(t[x].ch[0],k,dl,dm);
            else del(t[x].ch[1],k,dm,dr);
            upd(x);
            if (ifrbu(x)) rbu(x,dl,dr);
        }
        return;
    }
}
using namespace Scapegoat_tree;
using namespace std;
int q,cnt,mask,tmp;
char ch[2000001];

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

bool cmpp(char *str,int len,int x) {
    for (int i=1;i<=len;i++,x--) {
        if (str[i]>s[x]) return 0;
        if (str[i]<s[x]) return 1;
    }
    return 0;
}

int ask(int x,char *str,int len) {
    if (!x) return 0;
    if (cmpp(str,len,x)) return ask(t[x].ch[0],str,len);
    else return t[t[x].ch[0]].sizt+1+ask(t[x].ch[1],str,len);
}

int main() {
	freopen("P6164_3.in","r",stdin);
	freopen("1.out","w",stdout);
	
    scanf("%d",&q);
    scanf("%s",ch+1);
    int len=strlen(ch+1);
    for (int i=1;i<=len;i++) {
        s[++cnt]=ch[i];
        ins(rt,cnt,0,INF);
    }
    string opt;
    int i=1;
    while (q--) {
        int ans=0;
        cin>>opt;
        if (opt[0]=='A') {
            scanf("%s",ch+1);
            decode(ch+1,mask);
            int len=strlen(ch+1);
            for (int i=1;i<=len;i++) {
                s[++cnt]=ch[i];
                ins(rt,cnt,0,INF);
            }
//            cout<<ch+1<<endl;
        } else if (opt[0]=='D') {
            scanf("%d",&tmp);
            while (tmp) {
                del(rt,cnt,0,INF);
                cnt--,tmp--;
            }
        } else if (opt[0]=='Q') {
            scanf("%s",ch+1);
            decode(ch+1,mask);
            int len=strlen(ch+1);
            reverse(ch+1,ch+len+1);
            ch[len+1]='Z'+1;
            ch[len+2]=0;
            ans=ask(rt,ch,len+1);
            ch[len]--;
			ans-=ask(rt,ch,len+1);
            mask^=ans;
            printf("%d\n",ans);
// 			cout<<ch+1<<endl;
        }
        i++;
    }
    return 0;
}