#include <cstdio>

 #include <cmath>

 typedef unsigned long long LL;

 const double a=0.55;

 const LL inf=1ULL<<;

 const int sizeOfString=;

 const int sizeOfTree=;

 inline int getint();

 inline char getch();

 inline int getstr(char * );

 inline void putint(int);

 int n, q, len, type;

 char s[sizeOfString];

 int P[sizeOfString];

 inline void reverse();

 struct node {int p, s; LL tag; node * c[];};

 node memory_node[sizeOfString], * port_node=memory_node;

 node * root;

 node * suf[sizeOfString];

 inline node * newnode(int);

 inline bool cmp(int, int);

 inline bool cmp(node * , node * );

 node * flatten(node * , node * );

 node * build(node * , int);

 void print(node * );

 void rebuild(node *& );

 void remark(node * , LL, LL);

 bool insert(node *& , node * , LL=, LL=inf, int=);

 struct seg {int p; seg * l, * r;};

 seg memory_seg[sizeOfTree], * port_seg=memory_seg;

 seg * t;

 inline seg * newseg();

 inline int min(int, int);

 seg * build(int, int);

 void update(seg * , int, int, int);

 int query(seg * , int, int, int, int);

 int main()

 {

     int ans=;

     char ch;

     int c, x, pos, l, r;

     n=getint(), q=getint(), len=getint(), type=getint();

     getstr(s);

     reverse();

     root=suf[]=newnode();

     root->tag=(+inf)>>;

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

     {

         suf[i]=newnode(i);

         insert(root, suf[i]);

     }

     for (int i=;i<=n;i++) P[i]=getint();

     t=build(, n);

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

     {

         ch=getch();

         if (ch=='I')

         {

             c=getint(); if (type) c=c^ans;

             s[++len]=c+'a';

             suf[len]=newnode(len);

             insert(root, suf[len]);

         }

         if (ch=='C')

         {

             x=getint(); pos=getint();

             P[x]=pos;

             update(t, , n, x);

         }

         if (ch=='Q')

         {

             l=getint(); r=getint();

             ans=query(t, , n, l, r);

             putint(ans);

         }

     }

     return ;

 }

 inline int getint()

 {

     register int num=;

     register char ch;

     do ch=getchar(); while (ch<'' || ch>'');

     do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');

     return num;

 }

 inline char getch()

 {

     register char ch;

     do ch=getchar(); while (ch!='I' && ch!='C' && ch!='Q');

     return ch;

 }

 inline int getstr(char * str)

 {

     register int len=;

     register char ch;

     do ch=getchar(); while (ch<'a' || ch>'z');

     do str[++len]=ch, ch=getchar(); while (ch>='a' && ch<='z');

     return len;

 }

 inline void putint(int num)

 {

     char stack[];

     register int top=;

     for ( ;num;num/=) stack[++top]=num%+'';

     for ( ;top;top--) putchar(stack[top]);

     putchar('\n');

 }

 inline void reverse()

 {

     static char t[sizeOfString];

     for (int i=;i<=len;i++) t[i]=s[len-i+];

     for (int i=;i<=len;i++) s[i]=t[i];

 }

 inline node * newnode(int p)

 {

     node * ret=port_node++;

     ret->p=p; ret->s=;

     ret->tag=0LL;

     ret->c[]=NULL; ret->c[]=NULL;

     return ret;

 }

 inline bool cmp(int a, int b)

 {

     return suf[a]->tag<suf[b]->tag;

 }

 inline bool cmp(node * a, node * b)

 {

     return s[a->p]==s[b->p]?cmp(a->p-, b->p-):s[a->p]<s[b->p];

 }

 node * flatten(node * x, node * y)

 {

     if (!x) return y;

     x->c[]=flatten(x->c[], y);

     return flatten(x->c[], x);

 }

 node * build(node * x, int s)

 {

     node * y, * z;

     if (!s) return x->c[]=NULL, x;

     y=build(x, s>>); z=build(y->c[], s--(s>>));

     y->c[]=z->c[]; z->c[]=y;

     return z;

 }

 void rebuild(node *& t)

 {

     static node temp;

     node * line;

     int n=t->s;

     line=flatten(t, &temp);

     build(line, n);

     t=temp.c[];

 }

 void remark(node * t, LL l, LL r)

 {

     LL m=(l+r)>>;

     t->tag=m; t->s=;

     if (t->c[]) remark(t->c[], l, m), t->s+=t->c[]->s;

     if (t->c[]) remark(t->c[], m, r), t->s+=t->c[]->s;

 }

 bool insert(node *& t, node * x, LL l, LL r, int d)

 {

     LL m=(l+r)>>;

     bool ret=false;

     if (!t) x->tag=m, t=x, ret=d>(log(root->s)/log(1.0/a));

     else

     {

         t->s++;

         if (cmp(t, x)) ret=insert(t->c[], x, m, r, d+);

         else ret=insert(t->c[], x, l, m, d+);

         if (ret) if ((t->c[] && t->c[]->s>a*t->s) || (t->c[] && t->c[]->s>a*t->s))

         {

             rebuild(t);

             remark(t, l, r);

             ret=false;

         }

     }

     return ret;

 }

 inline seg * newseg()

 {

     seg * ret=port_seg++;

     ret->l=ret->r=NULL;

     return ret;

 }

 inline int min(int x, int y)

 {

     if (suf[P[x]]->tag<=suf[P[y]]->tag) return x;

     return y;

 }

 seg * build(int l, int r)

 {

     seg * t=newseg();

     if (l==r) return t->p=l, t;

     int m=(l+r)>>;

     t->l=build(l, m); t->r=build(m+, r);

     t->p=min(t->l->p, t->r->p);

     return t;

 }

 void update(seg * t, int l, int r, int p)

 {

     if (l==r) return ;

     int m=(l+r)>>;

     if (p<=m) update(t->l, l, m, p);

     else update(t->r, m+, r, p);

     t->p=min(t->l->p, t->r->p);

 }

 int query(seg * t, int l, int r, int ql, int qr)

 {

     if (l==ql && r==qr) return t->p;

     int m=(l+r)>>;

     if (qr<=m) return query(t->l, l, m, ql, qr);

     else if (ql>=m+) return query(t->r, m+, r, ql, qr);

     return min(query(t->l, l, m, ql, m), query(t->r, m+, r, m+, qr));

 }