懒得写背景了，给你一个字符串init，要求你支持两个操作
    
    (1):在当前字符串的后面插入一个字符串
    
    (2):询问字符串s在当前字符串中出现了几次？(作为连续子串)
    
    你必须在线支持这些操作。

第一行一个数Q表示操作个数
    
    第二行一个字符串表示初始字符串init
    
    接下来Q行，每行2个字符串Type,Str
    
    Type是ADD的话表示在后面插入字符串。
    
    Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。
    
    为了体现在线操作，你需要维护一个变量mask，初始值为0
   
    
    读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。
    询问的时候，对TrueStr询问后输出一行答案Result
    然后mask = mask xor Result 
    插入的时候，将TrueStr插到当前字符串后面即可。

HINT:ADD和QUERY操作的字符串都需要解压

A

QUERY B

ADD BBABBBBAAB

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

using namespace std;

#define MAXN 1210000

int pnt[MAXN],ch[MAXN][],pls[MAXN],val[MAXN];

bool rev[MAXN];

int stack[MAXN],tops=-;

bool is_root(int now)

{

        return !pnt[now] || (ch[pnt[now]][]!=now && ch[pnt[now]][]!=now);

}

void update(int){}

void make_reverse(int now)

{

        swap(ch[now][],ch[now][]);

        rev[now]^=;

}

void make_plus(int now,int v)

{

        val[now]+=v;

        pls[now]+=v;

}

void down(int now)

{

        if (rev[now])

        {

                make_reverse(ch[now][]);

                make_reverse(ch[now][]);

                rev[now]=;

        }

        if (pls[now])

        {

                make_plus(ch[now][],pls[now]);

                make_plus(ch[now][],pls[now]);

                pls[now]=;

        }

}

void rotate(int now)

{

        int p=pnt[now],anc=pnt[p];

        int dir=ch[p][]==now;

        if (!is_root(p))

                ch[anc][ch[anc][]==p]=now;

        pnt[now]=anc;

        pnt[ch[now][dir]]=p;

        ch[p][-dir]=ch[now][dir];

        pnt[p]=now;

        ch[now][dir]=p;

        update(p);

        update(now);

}

void splay(int now)

{

        int x=now;

        stack[++tops]=now;

        while (!is_root(x))

        {

                x=pnt[x];

                stack[++tops]=x;

        }

        while(~tops)

                down(stack[tops--]);

        while (!is_root(now))

        {

                int p=pnt[now],anc=pnt[p];

                if (is_root(p))

                        rotate(now);

                else if ((ch[anc][]==p) == (ch[p][]==now))

                        rotate(p),rotate(now);

                else

                        rotate(now),rotate(now);

        }

}

int access(int now)

{

        int son=;

        while (now)

        {

                splay(now);

                ch[now][]=son;

                update(now);

                son=now;

                now=pnt[now];

        }

        return son;

}

bool same_tree(int x,int y)

{

        while (pnt[x])x=pnt[x];

        while (pnt[y])y=pnt[y];

        return x==y;

}

void make_root(int now)

{

        make_reverse(access(now));

}

void path_plus(int x,int y,int v)

{

        //cout<<"Plus:"<<x<<" "<<y<<endl;

        assert(same_tree(x,y));

        make_root(x);

        make_plus(access(y),v);

}

void link(int x,int y)

{

        //cout<<"Link:"<<x<<" "<<y<<endl;

        assert(!same_tree(x,y));

        make_root(x),access(x);

        make_root(y),access(y);

        pnt[x]=y;

        ch[y][]=x;

}

void cut(int x,int y)

{

        //cout<<"Cut:"<<x<<" "<<y<<endl;

        assert(same_tree(x,y));

        make_root(x);

        access(y);

        ch[x][]=;

        pnt[y]=;

}

char str[MAXN],ss[MAXN];

struct sam_node

{

        int nxt[];

        int pnt;

        int len;

}sam[MAXN];

int topsam=;

int last=;

void Add_sam(char ch)

{

        register int p=last;

        register int np=++topsam;

        sam[np].len=sam[p].len+;

        val[np]=;

        while (p && !sam[p].nxt[ch-'A'])

        {

                sam[p].nxt[ch-'A']=np;

                p=sam[p].pnt;

        }

        if (!p)

        {

                last=np;

                sam[np].pnt=;

                link(np,sam[np].pnt);

        }else

        {

                register int q=sam[p].nxt[ch-'A'];

                if (sam[q].len==sam[p].len+)

                {

                        sam[np].pnt=q;

                        link(sam[np].pnt,np);

                        last=np;

                }else

                {

                        register int nq=++topsam;

                        splay(q);

                        val[nq]=val[q];

                        sam[nq]=sam[q];

                        link(sam[nq].pnt,nq);

                        sam[nq].len=sam[p].len+;

                        cut(sam[q].pnt,q);

                        /*ooo*/sam[q].pnt=nq;

                        link(sam[q].pnt,q);

                        /*ooo*/sam[np].pnt=nq;

                        link(sam[np].pnt,np);

                        while (p && sam[p].nxt[ch-'A']==q)

                        {

                                sam[p].nxt[ch-'A']=nq;

                                p=sam[p].pnt;

                        }

                        last=np;

                }

        }

        path_plus(,sam[np].pnt,);

}

char curs[MAXN];int totc=;

/*

   void dfs_sam(int now)

   {

   if (sam[now].flag)

   printf("%s\n",curs);

   for (int i=0;i<26;i++)

   {

   if (!sam[now].nxt[i])continue;

   curs[totc++]=(char)(i+'A');

   dfs_sam(sam[now].nxt[i]);

   curs[--totc]='\0';

   }

   }*/

int find_sam(char *str)

{

        int now=;

        while (*str)

        {

                if (!sam[now].nxt[*str-'A'])return ;

                assert(sam[now].nxt[*str-'A']);

                now=sam[now].nxt[*str-'A'];

                str++;

        }

        make_root(now);

        access(now);

        return val[now];

}

void Decode(char* str,int len,int mask)

{

        for (register int i=;i<len;i++)

        {

                mask=(mask*+i)%len;

                swap(str[i],str[mask]);

        }

}

char opt[];

char cc[MAXN];

int main()

{

        freopen("input.txt","r",stdin);

        int n,m,x,y,z;

        scanf("%d\n",&m);

        scanf("%s",str);

        int l=strlen(str);

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

                Add_sam(str[i]);

        /*

           for (int i=last;i;i=sam[i].pnt)sam[i].flag=true;

           dfs_sam(1);

           for (int i=0;i<l;i++)find_sam(str+i);*/

        int lastans=;

        for (int i=;i<m;i++)

        {

                scanf("%s %s\n",opt,cc);

                int t;

                t=strlen(cc);

                Decode(cc,t,lastans);

                if (opt[]=='Q')

                {

                        int now=;

                        printf("%d\n",t=find_sam(cc));

                        lastans^=t;

                }else

                {

                        int t=strlen(cc);

                        for (int i=;i<t;i++)

                                Add_sam(cc[i]);

                }

        }

}