#include<bits/stdc++.h>
using namespace std;
const int blsize=300;
struct blist
{
	int a[blsize*10],cnt[70010],blcnt[blsize*3],size,last,next;
}w[blsize*10];
int n,m,x,y,k,cnt2,cnt[70010],blcnt[blsize*3],last,st[blsize*3],ed[blsize*3],bl[70010];
char c[1];
int read()
{
	char ch=getchar();
	int r=0,w=1;
	while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
	return r*w;
}
void split(int x)
{
	w[++cnt2].size=w[x].size-blsize,w[x].size=blsize;
	w[cnt2].last=x,w[cnt2].next=w[x].next,w[x].next=cnt2,w[w[cnt2].next].last=cnt2;
//	cout<<w[x].next<<' '<<w[cnt2].next<<endl;
	memcpy(w[cnt2].cnt,w[x].cnt,sizeof(w[x].cnt));
	memcpy(w[cnt2].blcnt,w[x].blcnt,sizeof(w[x].blcnt));
	for(int i=1;i<=w[cnt2].size;i++)
	{
		w[cnt2].a[i]=w[x].a[i+blsize];
		w[x].cnt[w[cnt2].a[i]]--,w[x].blcnt[bl[w[cnt2].a[i]]]--;
	}
}
void insert(int x,int k)
{
	int blx=1;
	for(;w[blx].next&&x>w[blx].size;blx=w[blx].next)
	x-=w[blx].size;
	for(int i=w[blx].size;i>=x;i--)
	w[blx].a[i+1]=w[blx].a[i];
	w[blx].a[x]=k,w[blx].size++;
	for(int i=blx;i;i=w[i].next)
	w[i].cnt[k]++,w[i].blcnt[bl[k]]++;
	if(w[blx].size>=2*blsize)
	split(blx);
}
void add(int x,int k)
{
	int blx=1;
	for(;w[blx].next&&x>w[blx].size;blx=w[blx].next)
	x-=w[blx].size;
	for(int i=blx;i;i=w[i].next)
	w[i].cnt[w[blx].a[x]]--,w[i].blcnt[bl[w[blx].a[x]]]--,w[i].cnt[k]++,w[i].blcnt[bl[k]]++;
	w[blx].a[x]=k;
}
int ask(int x,int y,int k)
{
	int blx=1,bly=1;
	for(;w[blx].next&&x>w[blx].size;blx=w[blx].next)
	x-=w[blx].size;
	for(;w[bly].next&&y>w[bly].size;bly=w[bly].next)
	y-=w[bly].size;
	if(blx==bly)
	{
		for(int i=x;i<=y;i++)
		cnt[w[blx].a[i]]++,blcnt[bl[w[blx].a[i]]]++;
		for(int i=1;i<=blsize;i++)
		if(k<=blcnt[i])
		{
			for(int j=st[i];j<=ed[i];j++)
			if(k<=cnt[j])
			{
				for(int q=x;q<=y;q++)
				cnt[w[blx].a[q]]--,blcnt[bl[w[blx].a[q]]]--;
				return j;
			}
			else
			k-=cnt[j];
		}
		else
		k-=blcnt[i];
	}
	for(int i=x;i<=w[blx].size;i++)
	cnt[w[blx].a[i]]++,blcnt[bl[w[blx].a[i]]]++;
	for(int i=1;i<=y;i++)
	cnt[w[bly].a[i]]++,blcnt[bl[w[bly].a[i]]]++;
	for(int i=1;i<=blsize;i++)
	if(k<=blcnt[i]+w[w[bly].last].blcnt[i]-w[blx].blcnt[i])
	{
		for(int j=st[i];j<=ed[i];j++)
		if(k<=cnt[j]+w[w[bly].last].cnt[j]-w[blx].cnt[j])
		{
			for(int q=x;q<=w[blx].size;q++)
			cnt[w[blx].a[q]]--,blcnt[bl[w[blx].a[q]]]--;
			for(int q=1;q<=y;i++)
			cnt[w[bly].a[q]]--,blcnt[bl[w[bly].a[q]]]--;
			return j;
		}
		else
		k-=cnt[j]+w[w[bly].last].cnt[j]-w[blx].cnt[j];
	}
	else
	k-=blcnt[i]+w[w[bly].last].blcnt[i]-w[blx].blcnt[i];
}
int main()
{
	for(int i=1;i<=70005;i+=blsize)
	st[++cnt2]=i,ed[cnt2]=min(i+blsize-1,70005);
	for(int i=1;i<=cnt2;i++)
	for(int j=st[i];j<=ed[i];j++)
	bl[j]=i;
	n=read(),cnt2=bl[n];
	for(int i=1;i<bl[n];i++)
	w[i].next=i+1,w[i+1].last=i;
	for(int i=1;i<=n;i++)
	{
		w[bl[i]].size++,w[bl[i]].a[w[bl[i]].size]=read()+1;
		for(int j=bl[i];j;j=w[j].next)
		w[j].cnt[w[bl[i]].a[w[bl[i]].size]]++,w[j].blcnt[bl[w[bl[i]].a[w[bl[i]].size]]]++;
	}
	m=read();
	for(int i=1;i<=m;i++)
	{
		scanf("%s",c),x=read()^last,y=read()^last;
		if(c[0]=='Q')
		k=read()^last,printf("%d\n",last=ask(x,y,k)-1);
		else if(c[0]=='M')
		y++,add(x,y);
		else
		y++,insert(x,y);
	}
}