#include<bits/stdc++.h> 
using namespace std;
const int M=70010;
int n,opt,x,q,lans,ans;
vector<int>seq,num;
// SEG begin
struct SEG{
	int cnt=0;
	int siz[(int)5e6],ls[(int)5e6],rs[(int)5e6];
	void add(int &i,int l,int r,int x,int k){
		if(!i)i=++cnt;
		siz[i]+=k;if(l==r)return ;
		int mid=(l+r)>>1;
		if(x<=mid)add(ls[i],l,mid,x,k);
		else add(rs[i],mid+1,r,x,k);
	}
	void merge(int &i,int x,int y,int l,int r){
		if(!x&&!y)return ;
		if(!i)i=++cnt;siz[i]=siz[x]+siz[y];
		if(l==r)return ;
		int mid=(l+r)>>1;
		merge(ls[i],ls[x],ls[y],l,mid);
		merge(rs[i],rs[x],rs[y],mid+1,r);
		siz[i]=siz[ls[i]]+siz[rs[i]];
	}
	int get_kth(int l,int r,int k){
		if(l==r)return l;
		int mid=(l+r)>>1,s=0;
		for(auto x:seq)s+=siz[ls[x]];
		for(auto x:num)if(x<=mid)s++;
//		cout<<s;
		if(k<=s){for(auto &x:seq)x=ls[x];return get_kth(l,mid,k);}
		else {for(auto &x:seq)x=rs[x];for(auto &x:num)if(x<=mid)x=M;return get_kth(mid+1,r,k-s);}
	}
	void clean(int &i){i=0;return;}
}t;
// SEG end
double a=0.725;//平衡因子 
// SGT begin 
struct SGT{
	int R,cur,lc[(int)2e6],rc[(int)2e6],cnt[(int)2e6],siz[(int)2e6],tot[(int)2e6],val[(int)2e6],pos[(int)2e6];
	int g[(int)2e6],rt[(int)2e6],o=0;
	void aray(int x){if(!x)return ;aray(lc[x]);if(cnt[x])g[++o]=x;aray(rc[x]);}
	void up(int x){
		siz[x]=siz[lc[x]]+siz[rc[x]]+(cnt[x]?1:0);
		tot[x]=tot[lc[x]]+tot[rc[x]]+1;
		t.merge(rt[x],rt[lc[x]],rt[rc[x]],1,M);
		t.add(rt[x],1,M,val[x],1);
	}
	int build(int l,int r){
		if(l>r)return 0;
		if(l==r){lc[g[l]]=rc[g[l]]=0;up(g[l]);return g[l];}
		int mid=(l+r)>>1;
		lc[g[mid]]=build(l,mid-1),rc[g[mid]]=build(mid+1,r);
		up(g[mid]);return g[mid];
	}
	void rebuild(int &x){o=0;aray(x);x=build(1,o);}
	bool check(int x){return siz[x]&&(a*tot[x]<=max(tot[lc[x]],tot[rc[x]])||a*tot[x]>=siz[x]);}
	void add(int &i,int x,int X,int v){
//		cout<<i<<endl;
		if(!i){i=++cur;pos[i]=X;val[i]=v;t.add(rt[i],1,M,v,1);siz[i]++;tot[i]++;cnt[i]++;return;}
		t.add(rt[i],1,M,v,1),siz[i]++,tot[i]++;
		if(x<=siz[lc[i]]+1)add(lc[i],x,X,v);
		else add(rc[i],x-siz[lc[i]]-1,X,v);
		if(check(i))rebuild(i);
	}
	void change(int i,int x,int v){
		if(siz[lc[i]]+1==x){t.add(rt[i],1,M,val[i],-1),val[i]=v;t.add(rt[i],1,M,v,1);up(i);return ;}
		else if(x<=siz[lc[i]])change(lc[i],x,v);
		else change(rc[i],x-siz[lc[i]]-1,v);
		up(i);
	}
	int find(int i,int x){
		if(siz[lc[i]]+1==x)return val[i];
		else if(x<=siz[lc[i]])return find(lc[i],x);
		else return find(rc[i],x-siz[lc[i]]-1);
	}
	void get(int i,int l,int r,int x,int y){
		if(x>y||l>r)return ;if(!i)return ;
//		cout<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
//		cout<<lc[i]<<" "<<rc[i]<<endl;
		if(x<=l&&y>=r){seq.push_back(rt[i]);return ;}
		int mid=siz[lc[i]]+1;
//		cout<<mid<<endl;
		if(x<=mid&&y>=mid)num.push_back(val[i]);
		if(x<mid)get(lc[i],l,mid-1,x,y);
		if(y>mid)get(rc[i],mid+1,r,x,y);
	}
	int get_kth(int x,int y,int k){
//		cout<<siz[R]<<endl;
//		cout<<lc[R]<<" "<<rc[R]<<endl;
		get(R,1,siz[R],x,y);
//		for(auto x:seq)cout<<x<<" ";
//		cout<<endl;
//		for(auto x:num)cout<<x<<" ";
//		cout<<endl;
		return t.get_kth(1,M,k);
	}
	void debug(int nw){
		if(lc[nw])debug(lc[nw]);
		cout<<val[nw]-1<<" ";
		if(rc[nw])debug(rc[nw]);
	}
}T;
// SGT end 
int A;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>A,T.add(T.R,i,i,A+1);
	cin>>q;
	for(int i=1;i<=q;i++){
//		T.debug(T.R);
//		cout<<endl;
		char opt;
		cin>>opt;
		if(opt=='Q'){
			int x,y,k;
			cin>>x>>y>>k;
			x^=lans,y^=lans,k^=lans;
			lans=T.get_kth(x,y,k);lans--;
			cout<<lans<<'\n';
			num.clear(),seq.clear();
		}
		else if(opt=='M'){
			int x,v;
			cin>>x>>v;
			x^=lans,v^=lans;v++;
			T.change(T.R,x,v);
		}
		else {
			int x,v;
			cin>>x>>v;
			x^=lans,v^=lans;v++;
			T.add(T.R,x,x,v);
		}
	}
	return 0;
}