/*

动态求right集合的大小

LCT维护parent树即可

注意 由于树是有向的不会换根并且每次操作单一， 于是不需要维护子树和（写起来很麻烦）

直接打标记修改即可

*/

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<queue>

#define ll long long

#define M 1200010

#define mmp make_pair

using namespace std;

int read()

{

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int mask, ans;

struct Lct

{

	#define ls ch[x][0]

	#define rs ch[x][1]

	int ch[M][2], rev[M], ver[M], fa[M], s[M];

	bool isr(int x)

	{

		return ch[fa[x]][0] != x && ch[fa[x]][1] != x;

	}

	void up(int x, int vv)

	{

		ver[x] += vv;

		s[x] += vv;

	}

	void pushdown(int x)

	{

		if(s[x])

		{

			up(ls, s[x]);

			up(rs, s[x]);

			s[x] = 0;

		}

	}

	void pd(int x)

	{

		if(!isr(x)) pd(fa[x]);

		pushdown(x);

	}

	void rotate(int x)

	{

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

		bool dy = (ch[y][1] == x), dz = (ch[q][1] == y);

		if(!isr(y)) ch[q][dz] = x;

		fa[x] = q;

		fa[ch[x][dy ^ 1]] = y;

		ch[y][dy] = ch[x][dy ^ 1];

		ch[x][dy ^ 1] = y;

		fa[y] = x;

	}

	void splay(int x)

	{

		pd(x);

		while(!isr(x))

		{

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

			if(!isr(y))

			{

				if((ch[y][1] == x) ^ (ch[q][1] == y))

				{

					rotate(x);

				}

				else rotate(y);

			}

			rotate(x);

		}

	}

	void access(int x)

	{

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

	}

	void link(int x, int y)

	{

		fa[x] = y;

		access(y);

		splay(y);

		up(y, ver[x]);

	}

	void cut(int x)

	{

		access(x), splay(x), up(ls, -ver[x]), fa[ls] = 0, ls = 0;

	}

}T;

int ch[M][26], len[M], fa[M], lst = 1, cnt = 1;

void insert(int c)

{

	int p = ++cnt, f = lst;

	lst = p;

	len[p] = len[f] + 1;

	T.ver[p] = 1;

	while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];

	if(!f)

	{

		fa[p] = 1;

		T.link(p, 1);

	}

	else

	{

		int q = ch[f][c];

		if(len[q] == len[f] + 1)

		{

			T.link(p, q);

			fa[p] = q;

		}

		else

		{

			int nq = ++cnt;

			len[nq] = len[f] + 1;

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

			fa[nq] = fa[q];

			T.link(nq, fa[q]);

			fa[q] = fa[p] = nq;

			T.cut(q);

			T.link(q, nq);

			T.link(p, nq);

			while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];

		}

	}

}

char s[M * 3];

void work()

{

	int mlgb = mask;

	int l = strlen(s);

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

	{

		mlgb = (mlgb * 131 + i) % l;

		swap(s[i], s[mlgb]);

	}

//	puts(s);

}

int main()

{

	int q = read();

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

	int l = strlen(s + 1);

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

	while(q--)

	{

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

		if(s[1] == 'Q')

		{

			scanf("%s", s);

			l = strlen(s);

			work();

			int now = 1;

			for(int i = 0; i < l; i++) now = ch[now][s[i] - 'A'];

			if(!now) ans = 0;

			else

			{

				T.splay(now);

				ans = T.ver[now];

			}

			cout << ans << "\n";

			mask ^= ans;

		}

		else

		{

			scanf("%s", s);

			l = strlen(s);

			work();

			for(int i = 0; i < l; i++) insert(s[i] - 'A');

		}

	}

	return 0;

}

/*

2

BBABBBBAAB

ADD BBBAAB

QUERY BBA

*/