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;

}

int n,m;

#define MAXN 70010

#define N 70000

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

namespace SegT

{

	struct node

	{

		int lc,rc;

		int sum;

		node(){sum = 0;}

	}t[18000000];

	int ptr = 0;

	int del[18000000],del_ptr = 0;

	inline int newnode()

	{

		if(del_ptr != 0)

		{

			int k = del[del_ptr--];

			if(t[k].lc != 0)del[++del_ptr] = t[k].lc;

			if(t[k].rc != 0)del[++del_ptr] = t[k].rc;

			memset(&t[k],0,sizeof(t[k]));

			return k;

		}

		else return ++ptr;

	}

	inline void recycle(int &k)

	{

		del[++del_ptr] = k;

		k = 0;

		return; 

	}

	void insert(int &rt,int p,int k,int l,int r)

	{

		if(rt == 0)rt = newnode();

		t[rt].sum += k;

		if(t[rt].sum == 0){recycle(rt);return;}

		if(l == r)return;

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

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

		return;

	}

}

const double ALPHA = 0.77;

namespace ScaT

{

	struct node

	{

		int lc,rc,val,siz,wrt,srt;

	}t[MAXN];

	int root;

	int ptr = 0;

	inline int newnode(){return ++ptr;}

	int pos[MAXN],tot;

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

	{

		rt = 0;

		if(l > r)return;

		rt = pos[mid];

		for(register int i = l;i <= r;++i)SegT::insert(t[rt].srt,t[pos[i]].val,1,0,N);

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

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

		t[rt].siz = r - l + 1;

		return;

	}

	void getnode(int &rt)

	{

		if(rt == 0)return;

		getnode(t[rt].lc);

		pos[++tot] = rt;

		getnode(t[rt].rc);

		SegT::recycle(t[rt].srt);

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

		rt = 0;

		return;

	}

	void insert(int &rt,int p,int k,bool flag)

	{

		if(rt == 0)

		{

			rt = newnode();

			t[rt].val = k;t[rt].siz = 1;

			SegT::insert(t[rt].wrt,t[rt].val,1,0,N);

			SegT::insert(t[rt].srt,t[rt].val,1,0,N);

			return;

		}

		register bool tag = false;

		SegT::insert(t[rt].srt,k,1,0,N);

		++t[rt].siz;

		if(p <= t[t[rt].lc].siz)

		{

			tag = (t[t[rt].lc].siz + 1 >= (t[rt].siz + 1) * ALPHA);

			insert(t[rt].lc,p,k,tag || flag);

		}

		else

		{

			tag = (t[t[rt].rc].siz + 1 >= (t[rt].siz + 1) * ALPHA);

			insert(t[rt].rc,p - t[t[rt].lc].siz - 1,k,tag || flag);

		}

		if(!flag && tag)

		{

			tot = 0;getnode(rt);

			build(rt,1,tot);

		}

		return;

	}

	inline int getval(int rt,int p)

	{

		while(true)

		{

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

			else if(p > t[t[rt].lc].siz + 1)

			{

				p -= t[t[rt].lc].siz + 1;

				rt = t[rt].rc;

			}

			else return t[rt].val;

		}

	}

	inline void modify(int rt,int p,int x,int y)

	{//cout << x << " " << y << endl;

		while(true)

		{

			SegT::insert(t[rt].srt,x,-1,0,N);

			SegT::insert(t[rt].srt,y,1,0,N);

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

			else if(p > t[t[rt].lc].siz + 1)

			{

				p -= t[t[rt].lc].siz + 1;

				rt = t[rt].rc;

			}

			else

			{

				SegT::recycle(t[rt].wrt);

				SegT::insert(t[rt].wrt,y,1,0,N);

				t[rt].val = y;

				return;

			}

		}

	}

	int q[MAXN];

	void split(int rt,int l,int r)

	{

		if(l <= 1 && r >= t[rt].siz)

		{

			q[++q[0]] = t[rt].srt;

			return;

		}

		register int s = t[t[rt].lc].siz + 1;

		if(l <= s && r >= s)q[++q[0]] = t[rt].wrt;

		if(l < s)split(t[rt].lc,l,r);

		if(r > s)split(t[rt].rc,l - s,r - s);

		return;

	}

	inline int query(int k)

	{

		register int l = 0,r = N;

		while(l < r)

		{

			register int sum = 0;

			for(register int i = 1;i <= q[0];++i)sum += SegT::t[SegT::t[q[i]].lc].sum;

			if(k <= sum)

			{

				for(register int i = 1;i <= q[0];++i)q[i] = SegT::t[q[i]].lc;

				r = mid;

			}

			else

			{

				for(register int i = 1;i <= q[0];++i)q[i] = SegT::t[q[i]].rc;

				l = mid + 1;

				k -= sum;

			}

		}

		return l;

	}

}

inline char getc()

{

	register char c = getchar();

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

	return c;

}

void print(int k)

{

	if(k < 10)putchar(k + '0');

	else 

	{

		print(k / 10);

		putchar(k % 10 + '0');

	}

	return;

}

int main()

{freopen("1.in","r",stdin);freopen("kkk.out","w",stdout);

	scanf("%d",&n);

	using namespace ScaT;

	ptr = n;

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

	{

		pos[i] = i;t[i].val = rd();

		SegT::insert(t[i].wrt,t[i].val,1,0,N);

	}

	build(root,1,n);

	register char c;

	scanf("%d",&m);

	register int x,y,k;

	register int lastans = 0;

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

	{

		c = getc();

		if(c == 'Q')

		{

			x = rd() ^ lastans;y = rd() ^ lastans;k = rd() ^ lastans;

			q[0] = 0;

			split(root,x,y);

			lastans = query(k);

			print(lastans);puts("");

		}

		if(c == 'M')

		{

			x = rd() ^ lastans;k = rd() ^ lastans;

			modify(root,x,getval(root,x),k);

		}

		if(c == 'I')

		{

			x = rd() ^ lastans;k = rd() ^ lastans;

			insert(root,x - 1,k,false);

		}

	}

	return 0;

}