Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

char getc()

{

	register char c = getchar();

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

	return c;

}

int n,m,len,type;

#define MAXN 500010

int p[MAXN];

#define MAXL 800010

char c[MAXL];

#define N -100000000000000000000.0

#define F 100000000000000000000.0

typedef long double ld;

namespace BT

{

	struct node

	{

		int lc,rc;

		double val;

		int siz;

	}t[MAXL];

	bool cmp(int a,int b)

	{

		if(c[a] != c[b])return c[a] < c[b];

		else return t[a - 1].val < t[b - 1].val;

	}

	int root;

	int p[MAXL];

	void getp(int rt)

	{

		if(rt == 0)return;

		getp(t[rt].lc);

		p[++p[0]] = rt;

		getp(t[rt].rc);

		t[rt].lc = t[rt].rc = t[rt].siz = 0;

		return;

	}

	void build(int &rt,int l,int r)

	{

		if(l > r){rt = 0;return;}

		int mid = ((l + r) >> 1);

		rt = p[mid];

		t[rt].siz = 1;

		build(t[rt].lc,l,mid - 1);

		build(t[rt].rc,mid + 1,r);

		if(t[rt].lc)t[rt].siz += t[t[rt].lc].siz;

		if(t[rt].rc)t[rt].siz += t[t[rt].rc].siz;

		return;

	}

	void rebuild(int &rt)

	{//cout << t[rt].siz << " : ";

		p[0] = 0;

		getp(rt);//cout << p[0] << endl;

		build(rt,1,p[0]);

		return;

	}

	void insert(int &rt,int v,ld L,ld R,int tag)

	{

		if(rt == 0)

		{

			rt = v;

			t[rt].siz = 1;

			t[rt].val = (L + R) / 2;

			return;

		}

		int flag = tag;

		if(cmp(v,rt) && ((t[t[rt].lc].siz + 1) * 5 > (t[rt].siz + 1) * 4))tag = 1;

		if(!cmp(v,rt) && ((t[t[rt].rc].siz + 1) * 5 > (t[rt].siz + 1) * 4))tag = 1;

		if(cmp(v,rt))insert(t[rt].lc,v,L,t[rt].val,tag);

		else insert(t[rt].rc,v,t[rt].val,R,tag);

		t[rt].siz = 1;

		if(t[rt].lc)t[rt].siz += t[t[rt].lc].siz;

		if(t[rt].rc)t[rt].siz += t[t[rt].rc].siz;

		if(!flag && tag)rebuild(rt);

		return;

	}

}

#define fi first

#define se second

#define state pair<long double,int>

namespace ST

{

	struct node

	{

		int lc,rc;

		state s;

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)

		{

			t[rt].s.fi = BT::t[p[l]].val;

			t[rt].s.se = l;

			return;

		}

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		t[rt].s = min(t[t[rt].lc].s,t[t[rt].rc].s);

		return;

	}

	void add(int rt,int p,double val,int l,int r)

	{

		if(l == r){t[rt].s.fi = val;return;}

		if(p <= mid)add(t[rt].lc,p,val,l,mid);

		else add(t[rt].rc,p,val,mid + 1,r);

		t[rt].s = min(t[t[rt].lc].s,t[t[rt].rc].s);

		return;

	}

	state query(int rt,int L,int R,int l,int r)

	{

		if(L <= l && r <= R)return t[rt].s;

		if(R <= mid)return query(t[rt].lc,L,R,l,mid);

		if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

		return min(query(t[rt].lc,L,R,l,mid),query(t[rt].rc,L,R,mid + 1,r));

	}

}

int main()

{

	scanf("%d%d%d%d",&n,&m,&len,&type);

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

	for(int i = 1,j = len;i < j;++i,--j)swap(c[i],c[j]);

	for(int i = 1;i <= n;++i)scanf("%d",&p[i]);

	for(int i = 1;i <= len;++i)BT::insert(BT::root,i,N,F,0);

	ST::build(ST::root,1,n);

	int x,pos,l,r;

	char opt;

	int lastans = 0;

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

	{

		opt = getc();

		if(opt == 'I')

		{

			++len;

			c[len] = (rd() ^ (type * lastans)) + 'a';

			BT::insert(BT::root,len,N,F,0);

		}

		if(opt == 'C')

		{

			x = rd();pos = rd();

			p[x] = pos;

			ST::add(ST::root,x,BT::t[pos].val,1,n);

		}

		if(opt == 'Q')

		{

			l = rd();r = rd();

			lastans = ST::query(ST::root,l,r,1,n).se;

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

		}

	}

	return 0;

}