#include<cstdio>#include<algorithm>using namespace std;struct Data{	int p,v;}t[20010];int e,en=1;bool cmp(const Data &a,const Data &b){	return a.v<b.v;}int n,m,a[20010],ma[20010],x[10010],y[10010],z[10010];char op[10010][2];struct Node{int v,ch[2];}T[20010*195];int root[10010],now[2][10010];void Init_root(int ql,int qr){	--ql;	for(;ql;ql-=(ql&(-ql))) now[0][ql]=root[ql];	for(;qr;qr-=(qr&(-qr))) now[1][qr]=root[qr];}int qBIT(int K,int ql,int qr){	int res=0;	for(int x=ql-1;x;x-=(x&(-x))) res-=T[T[now[0][x]].ch[0]].v;	for(int x=qr;x;x-=(x&(-x))) res+=T[T[now[1][x]].ch[0]].v;	bool f=(res<K);	for(int x=ql-1;x;x-=(x&(-x))) now[0][x]=T[now[0][x]].ch[f];	for(;qr;qr-=(qr&(-qr))) now[1][qr]=T[now[1][qr]].ch[f];	return res;}int Kth(int K,int ql,int qr,int l,int r)//K小值{    if(l==r) return l;    int m=(l+r>>1),tmp;    if((tmp=qBIT(K,ql,qr))>=K) return Kth(K,ql,qr,l,m);    return Kth(K-tmp,ql,qr,m+1,r);}void Update(int p,int v,int cur,int l,int r){	if(l==r)	  {	  	T[cur].v+=v;	  	return;	  }	int m=(l+r>>1);	if(p<=m)	  {	  	if(!T[cur].ch[0]) T[cur].ch[0]=++e;	  	Update(p,v,T[cur].ch[0],l,m);	  }	else	  {	  	if(!T[cur].ch[1]) T[cur].ch[1]=++e;	  	Update(p,v,T[cur].ch[1],m+1,r);	  }	T[cur].v=T[T[cur].ch[0]].v+T[T[cur].ch[1]].v;}void Update(int pp,int p,int v){	for(;pp<=n;pp+=(pp&(-pp)))	  Update(p,v,root[pp],1,en);}int main(){//	freopen("bzoj1901.in","r",stdin);//	freopen("bzoj1901.out","w",stdout);	scanf("%d%d",&n,&m);	for(int i=1;i<=n;++i)	  scanf("%d",&t[i].v);	e=n;	for(int i=1;i<=m;++i)	  {	  	scanf("%s%d",op[i],&x[i]);	  	if(op[i][0]==‘C‘)	  	  scanf("%d",&t[++e].v);	  	else	  	  scanf("%d%d",&y[i],&z[i]);	  }	for(int i=1;i<=e;++i)	  t[i].p=i;	sort(t+1,t+e+1,cmp);	ma[a[t[1].p]=1]=t[1].v;	for(int i=2;i<=e;++i)	  {	  	if(t[i].v!=t[i-1].v)	  	  ++en;	  	ma[a[t[i].p]=en]=t[i].v;	  }	e=n;	for(int i=1;i<=m;++i)	  if(op[i][0]==‘C‘)	    z[i]=a[++e];	e=n;	for(int i=1;i<=n;++i)	  root[i]=i;	for(int i=1;i<=n;++i)	  Update(i,a[i],1);	for(int i=1;i<=m;++i)	  if(op[i][0]==‘C‘)	    {	      Update(x[i],a[x[i]],-1);	      a[x[i]]=z[i];	      Update(x[i],z[i],1);	    }	  else	    {	      Init_root(x[i],y[i]);	      printf("%d\n",ma[Kth(z[i],x[i],y[i],1,en)]);	    }	return 0;}