#include<cstdio>
#include<algorithm>
using namespace std;
#define mid (l+r>>1)
int n,m,rs,b[60000],q[10000][3];
char str[1000000],*p=str;
namespace CT{
	struct Node{Node*c[2];int s;}st[2500000],*stp,*T[50001];int S;
	Node*Build(int l=0,int r=S){Node*N=stp++;if(l+1!=r)N->c[0]=Build(l,mid),N->c[1]=Build(mid,r);return N;}
	inline Node*Insert(Node*y,int i,int j){
		Node*R=stp++,*x=R;int l=0,r=S;
		for(x->s=y->s+j;l+1!=r;x->s=y->s+j)if(i<mid)x->c[0]=stp++,x->c[1]=y->c[1],x=x->c[0],y=y->c[0],r=mid;
		else x->c[0]=y->c[0],x->c[1]=stp++,x=x->c[1],y=y->c[1],l=mid;
		return R;
	}struct ChairTree{
		Node*T[16];int s;
		inline ChairTree(){s=0;}
		inline ChairTree(Node*x){s=1;T[0]=x;}
		inline void operator+=(Node*x){T[s++]=x;}
		inline operator int()const{int i=s,ans=0;while(i--)ans+=T[i]->c[0]->s;return ans;}
		inline bool operator^=(bool c){int i=s;while(i--)T[i]=T[i]->c[c];return c;}
	};
}namespace BIT{
	CT::Node*A[50001];
	inline void Init(){int i=n;A[i]=CT::Build();while(--i)A[i]=A[n];}
	inline void I(int x,int i,int y){for(;x<=n;x+=x&-x)A[x]=CT::Insert(A[x],i,y);}
	inline void Q(CT::ChairTree&R,int x){for(;x;x-=x&-x)R+=A[x];}
}inline int getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}struct Q{int v,i;bool operator<(const Q&a)const{return v<a.v;}}rk[60000];
int main(){
	int i,j,l,r;bool C;fread(p,1,1000000,stdin);
	n=getint();m=getint();rs=0;CT::stp=CT::st;CT::S=1;
	for(i=-1;++i!=n;rs++)rk[rk[rs].i=rs].v=getint();
	for(i=m;i--;){
		while(*p!='Q'&&*p!='C')p++;
		if(*p=='Q')q[i][0]=getint(),q[i][1]=getint(),q[i][2]=getint();
		else q[i][0]=getint(),rk[rk[rs].i=rs].v=getint(),q[i][2]=0,rs++;
	}sort(rk,rk+rs);b[rk[0].i]=0;
	for(i=0;++i!=rs;b[rk[i].i]=CT::S-1)if(rk[i].v!=rk[i-1].v)rk[CT::S++].v=rk[i].v;
	BIT::Init();
	for(CT::T[rs=i=0]=BIT::A[n];i++!=n;)CT::T[i]=Insert(CT::T[i-1],b[rs++],1);
	while(m--)if(q[m][2]){
		CT::ChairTree a,b,c=CT::T[q[m][1]],d=CT::T[q[m][0]-1];
		BIT::Q(a,q[m][1]);
		BIT::Q(b,q[m][0]-1);
		for(l=0,r=CT::S;l+1!=r;a^=b^=c^=d^=C)if((i=a+c-b-d)>=q[m][2])C=0,r=mid;
		else C=1,l=mid,q[m][2]-=i;
		printf("%d\n",rk[l].v);
	}else{
		BIT::I(q[m][0],b[q[m][0]-1],-1);
		BIT::I(q[m][0],b[q[m][0]-1]=b[rs++],1);
	}return 0;
}