Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

#define MAXN 600010

int n;

namespace LCT

{

	struct node

	{

		int c[2],fa,tag,val;

		bool rev;

		node(){c[0] = c[1] = fa = tag = val = 0;rev = false;}

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	bool isroot(int x){return t[t[x].fa].c[0] != x && t[t[x].fa].c[1] != x;}

	int id(int x){return (t[t[x].fa].c[0] == x ? 0 : 1);}

	void connect(int x,int f,int p){t[x].fa = f;t[f].c[p] = x;return;}

	void pushdown(int x)

	{

		if(t[x].tag != 0)

		{

			if(t[x].c[0] != 0){t[t[x].c[0]].val += t[x].tag;t[t[x].c[0]].tag += t[x].tag;}

			if(t[x].c[1] != 0){t[t[x].c[1]].val += t[x].tag;t[t[x].c[1]].tag += t[x].tag;}

			t[x].tag = 0;

		}

		if(t[x].rev)

		{

			t[t[x].c[0]].rev ^= 1;t[t[x].c[1]].rev ^= 1;

			swap(t[x].c[0],t[x].c[1]);t[x].rev = false;

		}

		return;

	}

	void rotate(int x)

	{

		int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

		if(!isroot(y))t[z].c[fy] = x;

		t[x].fa = z;

		connect(t[x].c[fx ^ 1],y,fx);

		connect(y,x,fx ^ 1);

		return;

	}

	stack<int> s;

	void splay(int x)

	{

		s.push(x);

		for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

		while(!s.empty()){pushdown(s.top());s.pop();}

		while(!isroot(x))

		{

			int y = t[x].fa;

			if(isroot(y)){rotate(x);break;}

			if(id(x) == id(y)){rotate(y);rotate(x);}

			else{rotate(x);rotate(x);}

		}

		return;

	}

	void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;}return;}

	void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

	void add(int a,int b,int k){makeroot(a);access(b);splay(b);t[b].tag += k;t[b].val += k;return;}

	void link(int x,int f){makeroot(x);t[x].fa = f;add(1,f,t[x].val);return;}

	void cut(int x,int f){makeroot(x);access(f);splay(f);t[f].c[0] = t[x].fa = 0;add(1,f,-t[x].val);return;}

	int query(int a)

	{

		if(a == -1)return 0;

		makeroot(a);access(a);return t[a].val;

	}

}

namespace SAM

{

	struct node

	{

		int tr[26];

		int par,maxl;

	}s[MAXN << 1];

	int root = 1,ptr = 1,last = 1;

	int newnode(int k){++ptr;s[ptr].maxl = k;return ptr;}

	void extend(int k)

	{

		int p = last;

		int np = newnode(s[p].maxl + 1);LCT::t[np].val = 1;

		for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

		if(p == 0)

		{

			s[np].par = root;LCT::link(np,root); 

		}

		else

		{

			int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)

			{

				s[np].par = q;LCT::link(np,q);

			}

			else

			{

				int nq = newnode(s[p].maxl + 1);

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				s[nq].par = s[q].par;

				LCT::link(nq,s[q].par);

				LCT::cut(q,s[q].par);

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

				LCT::link(np,nq);LCT::link(q,nq);

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

			}

		}

		last = np;

		return;

	}

	int getpos(char c[])

	{

		int l = strlen(c);

		int cur = root;

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

		{

			if(s[cur].tr[c[i] - 'A'] == 0)return -1;

			cur = s[cur].tr[c[i] - 'A'];

		}

		return cur;

	}

}

char c[MAXN];

void read(int mask)

{

	int l = strlen(c);

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

	{

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

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

	}

	return;

}

int main()

{

	scanf("%d",&n);

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

	int mask = 0;

	int l = strlen(c + 1);

	for(int i = 1;i <= l;++i)SAM::extend(c[i] - 'A');

	char s[10];

	for(int i = 1;i <= n;++i)

	{

		scanf("%s",s);

		if(s[0] == 'A')

		{

			scanf("%s",c);

			read(mask);

			l = strlen(c);

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

			{

				SAM::extend(c[i] - 'A');

			}

		}

		else

		{

			scanf("%s",c);

			read(mask);

			l = strlen(c);

			int res = LCT::query(SAM::getpos(c));

			mask = mask ^ res;

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

		}

	}

	return 0;

}