#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int N=1e5+10;
const int C=320;
struct Block
{
	vector<int> a;
	int sums[N],sumc[C];
};
int n,m;
int limit=600,blo;
int bel[N];
int s[N],c[C],lst;
int T;
vector<Block> e;
inline void init()
{
	bel[0]=1;for (int i=1;i<=7e4;i++) bel[i]=(i-1)/C+1;
	return ;
}
inline void split(int loc)
{
	int x=e[loc].a.back();
	Block tmp;
	tmp.a.emplace_back(x);
	e.emplace(e.begin()+loc,tmp);blo++;
	e[loc+1].sums[x]++,e[loc+1].sumc[bel[x]]++;
	e[loc].a.pop_back();
	e[loc].sums[x]--,e[loc].sumc[bel[x]]--;
	return ;
}
inline void insert(int pos,int x)
{
	int loc=0;
	while (e[loc].a.size()<pos)
	{
		pos-=e[loc].a.size();
		loc++;
	}
	pos--;
	e[loc].a.emplace(e[loc].a.begin()+pos+1,x);
	e[loc].sums[x]++,e[loc].sumc[bel[x]]++;
	for (int i=loc+1;i<=blo;i++) e[i].sums[x]++,e[i].sumc[bel[x]]++;
	if (e[loc].a.size()>limit) split(loc);
	return ;
}
inline void emplace(int pos,int x)
{
	int loc=0;
//	cout<<"pos:"<<pos<<" loc"<<e[loc].a.size()<<endl;
	if (pos==m+1)
	{
		e.back().a.emplace_back(x);
		loc=blo;
	}
	else
	{
		while (e[loc].a.size()<pos)
		{
			pos-=e[loc].a.size();
			loc++;
		}
		pos--;
		e[loc].a.emplace(e[loc].a.begin()+pos,x);
	}
//	cout<<"pos:"<<pos<<endl;
//	if (e[loc].a.begin()+pos==e[loc].a.begin()) e[loc].a.(x);
//	e[loc].sums[x]++,e[loc].sumc[bel[x]]++;
	for (int i=loc;i<=blo;i++) e[i].sums[x]++,e[i].sumc[bel[x]]++;
	if (e[loc].a.size()>limit) split(loc);
	return ;
}
inline void update(int pos,int x)
{
	int loc=0;
	while (e[loc].a.size()<pos)
	{
		pos-=e[loc].a.size();
		loc++;
	}
	pos--;
	int pst=e[loc].a[pos];
	e[loc].sums[pst]--,e[loc].sumc[bel[pst]]--;
	e[loc].sums[x]++,e[loc].sumc[bel[x]]++;
	e[loc].a[pos]=x;
	for (int i=loc+1;i<=blo;i++) e[i].sums[pst]--,e[i].sumc[bel[pst]]--,e[i].sums[x]++,e[i].sumc[bel[x]]++;
	return ;
}
inline int query(int l,int r,int k)
{
	int bll=0;
	while (e[bll].a.size()<l)
	{
		l-=e[bll].a.size();
		bll++;
	}
	l--;
	int blr=0;
	while (e[blr].a.size()<r)
	{
		r-=e[blr].a.size();
		blr++;
	}
	r--;
	if (bll==blr)
	{
		for (int i=l;i<=r;i++) s[e[bll].a[i]]++,c[bel[e[bll].a[i]]]++;
		int siz=0,ll,rr;
		for (int i=1;i<=C+1;i++)
		{
			siz+=c[i];
			if (siz>=k)
			{
				siz-=c[i];
				ll=(i-1)*C+1;
				if (i==1) ll=0;
				rr=i*C;
				break;
			}
		}
		int ans=0;
		for (int i=ll;i<=rr;i++)
		{
			siz+=s[i];
			if (siz>=k)
			{
				ans=i;
				break;
			}
		}
		for (int i=l;i<=r;i++) s[e[bll].a[i]]--,c[bel[e[bll].a[i]]]--;
		return ans;
	}
	for (int i=l;i<e[bll].a.size();i++) s[e[bll].a[i]]++,c[bel[e[bll].a[i]]]++;
	for (int i=0;i<=r;i++) s[e[blr].a[i]]++,c[bel[e[blr].a[i]]]++;
	int siz=0,ll,rr;
	for (int i=1;i<=C+1;i++)
	{
		siz+=(c[i]+e[blr-1].sumc[i]-e[bll].sumc[i]);
		if (siz>=k)
		{
			siz-=(c[i]+e[blr-1].sumc[i]-e[bll].sumc[i]);
			ll=(i-1)*C+1;
			if (i==1) ll=0;
			rr=i*C;
			break;
		}
	}
	int ans=0;
	for (int i=ll;i<=rr;i++)
	{
		siz+=(s[i]+e[blr-1].sums[i]-e[bll].sums[i]);
		if (siz>=k)
		{
			ans=i;
			break;
		}
	}
	for (int i=l;i<e[bll].a.size();i++) s[e[bll].a[i]]--,c[bel[e[bll].a[i]]]--;
	for (int i=0;i<=r;i++) s[e[blr].a[i]]--,c[bel[e[blr].a[i]]]--;
	return ans;
}
signed main()
{
	init();
	cin>>n;
	int x;cin>>x;
	e.emplace_back();
	e.back().a.emplace_back(x);m++;
	e[0].sums[x]++,e[0].sumc[bel[x]]++;
	for (int i=2;i<=n;i++)
	{
		int x;
		cin>>x;
		insert(m++,x);
	}
//	split(0);
//	for (int i=0;i<e[0].a.size();i++) cout<<e[0].a[i]<<" ";
//	cout<<query(1,n,1)<<endl;
	cin>>T;
	while (T--)
	{
		char op;int x,val,l,r,k;
		cin>>op;
		if (op=='Q')
		{
			cin>>l>>r>>k;
			l^=lst,r^=lst,k^=lst;
//			for (int i=0;i<e.size();i++)
//				for (int j=0;j<e[i].a.size();j++)
//					cout<<e[i].a[j]<<" ";
//			cout<<endl;
			lst=query(l,r,k);
			cout<<lst<<endl;
		}
		if (op=='M')
		{
			cin>>x>>val;
			x^=lst,val^=lst;
			update(x,val);
//			for (int i=0;i<e.size();i++)
//				for (int j=0;j<e[i].a.size();j++)
//					cout<<e[i].a[j]<<" ";
		}
		if (op=='I')
		{
			cin>>x>>val;
			x^=lst,val^=lst;
			emplace(x,val);
			m++;
//			for (int i=0;i<e.size();i++)
//				for (int j=0;j<e[i].a.size();j++)
//					cout<<e[i].a[j]<<" ";
		}
	}
//	for (int i=0;i<e.size();i++)
//		for (int j=0;j<e[i].a.size();j++)
//			cout<<e[i].a[j]<<" ";
	return (0-0);
}

已经不知道该怎么调了。