#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int N=1e5+5;
int n,m,a[N],b[N<<1],tot,rt[N],cnt;
vector<int> t1,t2;
char st[4];
struct segtree{int sum,l,r;}tr[N*300];
struct que{int l,r,k,ff;}q[N];
void add(int &p,int l,int r,int x,int z){
	if(!p)p=++cnt;
	if(l==r){
		tr[p].sum+=z;
		return;
	}
	if(x<=mid)add(tr[p].l,l,mid,x,z);
	else add(tr[p].r,mid+1,r,x,z);
	tr[p].sum=tr[tr[p].l].sum+tr[tr[p].r].sum;
}
void Add(int x,int y,int z){for(;x<=n;x+=x&-x)add(rt[x],1,tot,y,z);}
int ask(int p,int l,int r,int L,int R){
	if(!p)return 0;
	if(l>=L&&r<=R)return tr[p].sum;
	return (L<=mid?ask(tr[p].l,l,mid,L,R):0)+(R>mid?ask(tr[p].r,mid+1,r,L,R):0);
}
int Ask(int l,int r,int k){
	if(l==r)return l;
	int sum=0;
	for(int i:t1)sum-=tr[tr[i].l].sum;
	for(int i:t2)sum+=tr[tr[i].l].sum;
	if(sum>=k){
		for(int i=0;i<t1.size();i++)t1[i]=tr[t1[i]].l;
		for(int i=0;i<t2.size();i++)t2[i]=tr[t2[i]].l;
		return Ask(l,mid,k);
	}
	else {
		for(int i=0;i<t1.size();i++)t1[i]=tr[t1[i]].r;
		for(int i=0;i<t2.size();i++)t2[i]=tr[t2[i]].r;
		return Ask(mid+1,r,k-sum);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
	tot=n;
	for(int i=1;i<=m;i++){
		scanf("%s",st+1);
		if(st[1]=='C'){
			q[i].ff=1;
			scanf("%d%d",&q[i].l,&q[i].k);
			b[++tot]=q[i].k;
		}
		else scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
	}
	sort(b+1,b+tot+1);//先离散化
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
		Add(i,a[i],1);//建树
	}
	for(int i=1;i<=m;i++){
		if(q[i].ff){
			Add(q[i].l,a[q[i].l],-1);
			a[q[i].l]=lower_bound(b+1,b+tot+1,q[i].k)-b;
			Add(q[i].l,a[q[i].l],1);
		}
		else{
			t1.clear(),t2.clear();
			for(int j=q[i].l-1;j;j-=j&-j)t1.push_back(rt[j]);//找到需要前缀和的树是那些
			for(int j=q[i].r;j;j-=j&-j)t2.push_back(rt[j]);
			printf("%d\n",b[Ask(1,tot,q[i].k)]);
		}
	}
}