#include<iostream>
#include<stdio.h>
#include<algorithm>
#define N 100005
using namespace std;
struct segment_tree{
	int lc,rc,sum;
}d[N*40];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
inline char readch(){
	char ch=getchar();
	while(ch!='Q' && ch!='C') ch=getchar();
	return ch;
}
int n,m,rt[N],pool,a[N],lsh[N*2],_n,t[N][2],cnt[2],q[N][3];
char op[N];
int lowbit(int x){return x&-x;}
void update(int &k,int l,int r,int x,int v){
	if(!k) k=++pool;
	if(l==r){
		d[k].sum=d[k].sum+v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) update(d[k].lc,l,mid,x,v);
	else update(d[k].rc,mid+1,r,x,v);
	d[k].sum=d[d[k].lc].sum+d[d[k].rc].sum;
}
void modify(int x,int v,int val){
	for(int i=x;i<=n;i+=lowbit(i)) update(rt[i],1,_n,v,val);
}
int query(int l,int r,int v){
	if(l==r) return l;
	int res,mid=l+r>>1;
	for(int i=1;i<=cnt[1];++i) res+=d[d[t[i][1]].lc].sum;
	for(int i=1;i<=cnt[0];++i) res-=d[d[t[i][0]].lc].sum;
	if(v<=res){
		for(int i=1;i<=cnt[0];++i) t[i][0]=d[t[i][0]].lc;
		for(int i=1;i<=cnt[1];++i) t[i][1]=d[t[i][1]].lc;
		return query(l,mid,v);
	}
	else{
		for(int i=1;i<=cnt[0];++i) t[i][0]=d[t[i][0]].rc;
		for(int i=1;i<=cnt[1];++i) t[i][1]=d[t[i][1]].rc;
		return query(mid+1,r,v-res);
	}
}
int solve(int x,int y,int z){
	cnt[0]=cnt[1]=0;
	for(int i=x-1;i;i-=lowbit(i)) t[++cnt[0]][0]=rt[i];
	for(int i=y;i;i-=lowbit(i)) t[++cnt[1]][1]=rt[i];
	return query(1,_n,z);
}
int main(){
	_n=n=read(),m=read();
	for(int i=1;i<=n;++i){
		lsh[i]=a[i]=read();
	}
	for(int i=1;i<=m;++i){
		op[i]=readch();
		q[i][0]=read(),q[i][1]=read();
		if(op[i]=='Q'){
			q[i][2]=read();
		}
		else{
			lsh[++_n]=q[i][1];
		}
	}
	sort(lsh+1,lsh+_n+1);
	_n=unique(lsh+1,lsh+_n+1)-lsh-1;
	for(int i=1;i<=n;++i)
		a[i]=lower_bound(lsh+1,lsh+_n+1,a[i])-lsh;
	for(int i=1;i<=n;++i) modify(i,a[i],1);
	for(int i=1;i<=m;++i){
		if(op[i]=='C'){
			q[i][1]=lower_bound(lsh+1,lsh+_n+1,q[i][1])-lsh;
			modify(q[i][0],a[q[i][0]],-1);
			a[q[i][0]]=q[i][1];
			modify(q[i][0],a[q[i][0]],1);
		}
		else{
			printf("%d\n",lsh[solve(q[i][0],q[i][1],q[i][2])]);
		}
	}
	return 0;
}