rt

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,lenn,lenm,id[200005],ID[200005],pt[200005],b[200005],lsh[200005],tmp,maxi=-1e18;//id[i]表示第 i 个数是第几个序列块，ID[i]表示第 i 个数是第几个值域块 
int sum[505][505],s[505][200005],S[505];//sum[i][j]表示前 i 块中大小在值域第 j 块的数的数量 ，s[i][j]表示前 i 块中大小为 j 的数的个数，S[i]表示散块的临时数组 
int a[200005];
struct node{
	char c;
	int l,r,k;
}q[200005];
void help(){
	for(int i=1; i<=tmp; i++)
		lsh[i]=b[i];
	sort(lsh+1,lsh+tmp+1);
	int len=unique(lsh+1,lsh+tmp+1)-(lsh+1);
	for(int i=1; i<=tmp; i++)
		pt[lower_bound(lsh+1,lsh+len+1,b[i])-lsh]=b[i],b[i]=lower_bound(lsh+1,lsh+len+1,b[i])-lsh,maxi=max(maxi,b[i]);
	return;
}
int qr(int lt,int rt,int val){//求第 lt 到 rt 块中第 val 块所有数的出现次数之和 
	return sum[rt][val]-sum[lt-1][val];
}
int QR(int lt,int rt,int val){//求第 lt 到 rt 块中值为 val 的数的出现次数 
	return s[rt][val]-s[lt-1][val];
}
void init(){
	for(int i=1; i<=id[n]; i++){
		for(int j=1; j<=ID[n+m]; j++)
			sum[i][j]=sum[i-1][j];//继承前i-1块 
		for(int j=(i-1)*lenn+1; j<=i*lenn; j++)
			sum[i][(a[j]-1)/lenm+1]++;//算当前块的贡献 
	}
	for(int i=1; i<=id[n]; i++){
		for(int j=1; j<=200000; j++)
			s[i][j]=s[i-1][j];//继承第 i-1 块 
		for(int j=(i-1)*lenn+1; j<=i*lenn; j++)
			s[i][a[j]]++;//算当前块的贡献 
	}
	return;
}
void update(int cur,int val){//将第 cur 个数修改为 val
	for(int i=id[cur]; i<=id[n]; i++)
		sum[i][(val-1)/lenm+1]++,sum[i][(a[cur]-1)/lenm+1]--,s[i][val]++,s[i][a[cur]]--;//更新前 i 块的贡献 
	a[cur]=val;
	return;
}
int query(int lt,int rt,int k){
	memset(S,0,sizeof S);
	if(id[lt]==id[rt]){
		for(int i=lt; i<=rt; i++)
			S[(a[i]-1)/lenm+1]++;
		int l=0;
		for(int i=1; i<=ID[n+m]; i++){
			l+=S[i];
			if(l>=k){
				l-=S[i];
				k-=l;
				memset(S,0,sizeof S);
				for(int i=lt; i<=rt; i++)
					S[a[i]]++;
				for(int j=(i-1)*lenm+1; j<=i*lenm; j++){
					if(k>S[j])
						k-=S[j];
					else
						return j;
				}
			}
		}
		return -114514;
	}
	for(int i=lt; id[i]==id[lt]; i++)
		S[(a[i]-1)/lenm+1]++;
	for(int i=rt; id[i]==id[rt]; i--)
		S[(a[i]-1)/lenm+1]++;
	for(int i=1; i<=ID[n+m]; i++){
		if(S[i]+qr(id[lt]+1,id[rt]-1,i)<k)
			k-=(S[i]+qr(id[lt]+1,id[rt]-1,i));
		else{
			memset(S,0,sizeof S);
			for(int i=lt; id[i]==id[lt]; i++)
				S[a[i]]++;
			for(int i=rt; id[i]==id[rt]; i--)
				S[a[i]]++;
			for(int j=(i-1)*lenm+1; j<=i*lenm; j++){
				if(S[j]+QR(id[lt]+1,id[rt]-1,j)<k)
					k-=(S[j]+QR(id[lt]+1,id[rt]-1,j));
				else
					return j;
			}
			return -1;
		}
	}
}
signed main(){
	cin>>n>>m;
	lenn=sqrt(n);
	lenm=sqrt(n+m);
	tmp=n;
	for(int i=1; i<=n+m; i++)
		ID[i]=(i-1)/lenm+1;
	for(int i=1; i<=n; i++)
		cin>>a[i],lsh[i]=a[i],id[i]=(i-1)/lenn+1,b[i]=a[i];
	for(int i=1; i<=m; i++){
		cin>>q[i].c;
		if(q[i].c=='Q')
			cin>>q[i].l>>q[i].r>>q[i].k;
		else
			cin>>q[i].l>>q[i].k,b[++tmp]=q[i].k;
	}
	help();
	for(int i=1; i<=n; i++)
		a[i]=b[i];
	int nw=1;
	for(int i=1; i<=m; i++)
		if(q[i].c=='C')
			q[i].k=b[n+nw],nw++;
	init();
	for(int i=1; i<=m; i++){
		if(q[i].c=='Q')
			cout<<pt[query(q[i].l,q[i].r,q[i].k)]<<'\n';
		else
			update(q[i].l,q[i].k);
	}
	return 0;
}