#include <bits/stdc++.h>
#define N 1365872
using namespace std;

namespace Link_Cut_Tree{
    #define pa p[nd]
    #define root nd[0].c[0]
    struct node{
        int v, tv, c[2], p;
    }nd[N];
    inline int dir(int x){return !x[nd].p ? -1 : x == x[nd].pa.c[0] ? 0 : x == x[nd].pa.c[1] ? 1 : -1;}
    void add(int x, int v){x[nd].v += v; x[nd].tv += v;}
    void push_down(int x){if(x[nd].tv){add(x[nd].c[0], x[nd].tv); add(x[nd].c[1], x[nd].tv); x[nd].tv = 0;}}
    void pull_down(int x){if(~dir(x)) pull_down(x[nd].p); push_down(x);}
    void rotate(int x){
        int y = x[nd].p, d = !dir(x);
        nd[y[nd].c[!d] = x[nd].c[d]].p = y;
        x[nd].p = y[nd].p;
        if(~dir(y)) y[nd].pa.c[dir(y)] = x;
        nd[x[nd].c[d] = y].p = x;
    }
    void splay(int x){for(pull_down(x); ~dir(x); rotate(x))
        if(~dir(x[nd].p)) rotate(dir(x) ^ dir(x[nd].p) ? x : x[nd].p);}
    void access(int x){for(int y = 0; x; y = x, x = x[nd].p){splay(x); x[nd].c[1] = y;}}
    void link(int x, int y){x[nd].p = y; access(y); splay(y); add(y, x[nd].v);}
    void cut(int x){access(x); splay(x); int &y = x[nd].c[0]; add(y, -x[nd].v); y = y[nd].p = 0;}
    #undef pa
    #undef root
}

namespace Suffix_Automaton{
    #define q d[p][x]
    int cnt = 1, p, np = 1, pa[N], d[N][26], val[N];
    void extend(int x){
        for(p = np, val[np = ++cnt] = val[p] + 1; p && !q; q = np, p = pa[p]);
        Link_Cut_Tree::nd[np].v = 1;
        if(!p){
            pa[np] = 1;
            Link_Cut_Tree::link(np, 1);
        }else
            if(val[p] + 1 == val[q]){
                pa[np] = q;
                Link_Cut_Tree::link(np, q);
            }else{
                int nq = ++cnt;
                val[nq] = val[p] + 1;
                memcpy(d[nq], d[q], 104);
                pa[nq] = pa[q];
                Link_Cut_Tree::link(nq, pa[q]);
                pa[np] = pa[q] = nq;
                Link_Cut_Tree::cut(q);
                Link_Cut_Tree::link(np, nq);
                Link_Cut_Tree::link(q, nq);
                for(int Q = q; p && q == Q; q = nq, p = pa[p]);
            }
    }
    #undef q
}

int n, p, q, i, ans, mask;
char s[N], op[6];

void getstr(){
    int i, t;
    scanf("%s", s);
    n = strlen(s);
    for(t = mask % n, i = 0; i < n; i++){
        t = (t * 131 + i) % n;
        swap(s[i], s[t]);
    }
}

int main(){
    scanf("%d%s", &q, s);
    n = strlen(s);
    for(i = 0; i < n; i++)
        Suffix_Automaton::extend(s[i] - 'A');
    for(mask = 0; q; --q){
        scanf("%s", op);
        getstr();
        if(op[0] == 'A')
            for(i = 0; i < n; i++)
                Suffix_Automaton::extend(s[i] - 'A');
        else{
            p = 1;
            for(i = 0; i < n; i++)
                if(!(p = Suffix_Automaton::d[p][s[i] - 'A'])) break;
            if(i == n){
                Link_Cut_Tree::splay(p);
                printf("%d\n", ans = Link_Cut_Tree::nd[p].v);
                mask ^= ans;
            }else
                puts("0");
        }
    }
}