rt

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7,M=320,K=450;
int a[N],b[N*2],s[M][N],sk[M][K],f[N],fk[K],n,q,k,sz,m,szk,mk;
int lb[M],rb[M],bl[N],lbk[K],rbk[K],blk[N*2],op[N],ql[N],qr[N],qk[N];
char ops[5];
void update(int x,int y){
	int z=a[x];
	for (int i=bl[x];i<=m;++i){
		--s[i][z],--sk[i][blk[z]];
		++s[i][y],++sk[i][blk[y]];
	}
	a[x]=y;
}
int query(int l,int r,int k){
	int lk=bl[l],rk=bl[r],p=0,ans=0;
	if (lk==rk){
		for (int i=l;i<=r;++i)
			++f[a[i]],++fk[blk[a[i]]];
		for (int i=0;i<=mk;++i){
			if (k<=fk[i]) {p=i;break;}
			k-=fk[i];
		}
		for (int i=lbk[p];i<=rbk[p];++i){
			if (k<=f[i]) {ans=i;break;}
			k-=f[i];
		}
		for (int i=l;i<=r;++i)
			f[a[i]]=fk[blk[a[i]]]=0;
		return ans;
	}
	for (int i=l;i<=rb[lk];++i)
		++f[a[i]],++fk[blk[a[i]]];
	for (int i=lb[rk];i<=r;++i)
		++f[a[i]],++fk[blk[a[i]]];
	for (int i=0;i<=mk;++i){
		int x=fk[i]+sk[rk-1][i]-sk[lk][i];
		if (k<=x) {p=i;break;}
		k-=x;
	}
	for (int i=lbk[p];i<=rbk[p];++i){
		int x=f[i]+s[rk-1][i]-s[lk][i];
		if (k<=x) {ans=i;break;}
		k-=x;
	}
	for (int i=l;i<=rb[lk];++i)
		f[a[i]]=fk[blk[a[i]]]=0;
	for (int i=lb[rk];i<=r;++i)
		f[a[i]]=fk[blk[a[i]]]=0;
	return ans;
}
signed main(){
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;++i)
		scanf("%d",a+i),b[++k]=a[i];
	for (int i=1;i<=q;++i){
		scanf("%s%d%d",ops,ql+i,qr+i);
		if (*ops=='C') op[i]=1,b[++k]=qr[i];
		else op[i]=2,scanf("%d",qk+i);
	}
	sort(b+1,b+k+1),k=unique(b+1,b+k+1)-b-1;
	for (int i=1;i<=n;++i)
		a[i]=lower_bound(b+1,b+k+1,a[i])-b;
	for (int i=1;i<=q;++i)
		if (op[i]==1) qr[i]=lower_bound(b+1,b+k+1,qr[i])-b;
	sz=sqrt(n),m=n/sz,szk=sqrt(k),mk=k/szk;
	for (int i=0;i<=m;++i){
		lb[i]=max(1,i*sz),rb[i]=min(n,i*sz+sz-1);
		for (int j=lb[i];j<=rb[i];++j)
			bl[j]=i;
	}
	for (int i=0;i<=mk;++i){
		lbk[i]=max(1,i*szk),rbk[i]=min(k,i*szk+szk-1);
		for (int j=lbk[i];j<=rbk[i];++j)
			blk[j]=i;
	}
	for (int i=0;i<=m;++i){
		for (int j=1;j<=k;++j)
			s[i][j]=(i ? s[i-1][j] : 0);
		for (int j=1;j<=mk;++j)
			sk[i][j]=(i ? sk[i-1][j] : 0);
		for (int j=lb[i];j<=rb[i];++j)
			++s[i][a[j]],++sk[i][blk[a[j]]];
	}
	for (int i=1;i<=q;++i){
		if (op[i]==1) update(ql[i],qr[i]);
		else printf("%d\n",b[query(ql[i],qr[i],qk[i])]);
	}
	return 0;
}