rt

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;

char op[N];
int ql[N],qr[N],qk[N];

int root[N<<2];

int tot;
int son[4000005][2],fa[4000005];
int val[4000005],cnt[4000005],size[4000005];

int n,m;
int a[N],A[N],len;

inline int Q(int x){return lower_bound(A+1,A+1+len,x)-A;}

inline void update(int x){
	size[x]=size[son[x][0]]+size[son[x][1]]+cnt[x];
}
inline int get(int x){
	return x==son[fa[x]][1];
}
inline void clear(int x){
	son[x][0]=son[x][1]=fa[x]=val[x]=cnt[x]=size[x]=0;
}

inline void rotate(int x){
	int y=fa[x],z=fa[y],k=get(x);
	son[y][k]=son[x][k^1];
	if(son[x][k^1])
		fa[son[x][k^1]]=y;
	son[x][k^1]=y;
	fa[y]=x;
	fa[x]=z;
	if(z)
		son[z][y==son[z][1]]=x;
	update(y);
	update(x);
}
inline void splay(int x,int& root){
	int y=fa[x];
	while(y){
		if(fa[y])
			rotate(get(x)==get(y)?y:x);
		rotate(x);
		y=fa[x];
	}
	root=x;
}
inline void insert(int v,int& root){
	if(!root){
		tot++;
		val[tot]=v;
		cnt[tot]=1;
		update(tot);
		root=tot;
		return;
	}
	int cur=root,x=0;
	while(true){
		if(val[cur]==v){
			cnt[cur]++;
			update(cur);
			if(x)update(x);
			splay(cur,root);
			break;
		}
		x=cur;
		cur=son[cur][val[cur]<v];
		if(!cur){
			tot++;
			son[x][val[x]<v]=tot;
			fa[tot]=x;
			val[tot]=v;
			cnt[tot]=1;
			update(tot);
			update(x);
			splay(tot,root);
			break; 
		}
	}
}
inline int pre(int& root){
	int cur=son[root][0];
	if(!cur)return root;
	while(son[cur][1])
		cur=son[cur][1];
	splay(cur,root);
	return cur;
}
inline void find(int v,int& root){
	int cur=root;
	while(true){
		if(val[cur]==v){
			splay(cur,root);
			return;
		}
		cur=son[cur][val[cur]<v];
	}
}
inline int get_sum(int v,int& root){
	if(v==0)return 0;
	int res=0,cur=root;
	while(true){
		if(val[cur]==v){
			res+=size[son[cur][0]]+cnt[cur];
			splay(cur,root);
			return res;
		}
		if(v<val[cur]){
			cur=son[cur][0];
		}else{
			res+=size[son[cur][0]]+cnt[cur];
			cur=son[cur][1];
		}
		if(!cur)return res;
	}
}
inline void erase(int v,int& root){
	find(v,root);
	if(cnt[root]>1){
		cnt[root]--;
		return;
	}
	if(!son[root][0]&&!son[root][1]){
		clear(root);
		root=0;
		return;
	}
	if(!son[root][0]){
		int cur=root;
		root=son[root][1];
		fa[root]=0;
		clear(cur);
		return;
	}
	if(!son[root][1]){
		int cur=root;
		root=son[root][0];
		fa[root]=0;
		clear(cur);
		return;
	}
	int cur=root;
	int x=pre(root);
	son[x][1]=son[cur][1];
	fa[son[cur][1]]=x;
	clear(cur);
	update(root);
}

inline void sIns(int x,int lt,int rt,int i,int v){
	insert(v,root[x]);
	if(lt==rt)return;
	int mid=lt+rt>>1;
	if(i<=mid)sIns(x<<1,lt,mid,i,v);
	else sIns(x<<1|1,mid+1,rt,i,v);
}
inline void sErs(int x,int lt,int rt,int i,int v){
	erase(v,root[x]);
	if(lt==rt)return;
	int mid=lt+rt>>1;
	if(i<=mid)sErs(x<<1,lt,mid,i,v);
	else sErs(x<<1|1,mid+1,rt,i,v);
}
inline int sQry(int x,int lt,int rt,int l,int r,int k){
	if(lt==rt)return val[root[x]];
	int mid=lt+rt>>1,s=get_sum(r,root[x<<1])-get_sum(l-1,root[x<<1]);
	if(k<=s)return sQry(x<<1,lt,mid,l,r,k);
	else return sQry(x<<1|1,mid+1,rt,l,r,k-s);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		A[++len]=a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>op[i];
		scanf("%d%d",&ql[i],&qr[i]);
		if(op[i]=='Q')
			scanf("%d",&qk[i]);
		else
			A[++len]=qr[i];
	}
	sort(A+1,A+1+len);
	len=unique(A+1,A+1+len)-A-1;
	for(int i=1;i<=n;i++){
		a[i]=Q(a[i]);
		sIns(1,1,len,a[i],i);	
	}
	for(int i=1;i<=m;i++){
		if(op[i]=='Q'){
			printf("%d\n",A[a[sQry(1,1,len,ql[i],qr[i],qk[i])]]);
		}else{
			sIns(1,1,len,Q(qr[i]),ql[i]);
			sErs(1,1,len,a[ql[i]],ql[i]);
			a[ql[i]]=Q(qr[i]);
		} 
	}
	return 0;
}