#include<iostream>
using namespace std;
const int N=100100,Log=35;
int L[N*Log],R[N*Log],ls[N*Log],rs[N*Log],val[N*Log],top[N],p[N],cnt;
inline int New(int L_,int R_,int ls_,int rs_){
	L[++cnt]=L_,R[cnt]=R_,ls[cnt]=ls_,rs[cnt]=rs_;
	return cnt;
}
inline void push_up(int nd){val[nd]=val[ls[nd]]+val[rs[nd]];}
void add(int nd,int pos,int k){
	if(L[nd]==R[nd]){val[nd]+=k;return;}
	int mid=(L[nd]+R[nd])>>1;
	if(!ls[nd])ls[nd]=New(L[nd],mid,0,0);
	if(!rs[nd])rs[nd]=New(mid+1,R[nd],0,0);
	if(pos<=mid)add(ls[nd],pos,k);
	else add(rs[nd],pos,k);
	push_up(nd);
}
int n,q,a[N];
inline void update(int i,int pos,int k){while(i<=n)add(top[i],pos,k),i+=i&-i;}
inline int get_ls(int i){int r=0;while(i)r+=ls[p[i]]?val[ls[p[i]]]:0,i-=i&-i;return r;}
inline void to_ls(int i){while(i)p[i]=ls[p[i]],i-=i&-i;}
inline void to_rs(int i){while(i)p[i]=rs[p[i]],i-=i&-i;}
inline void to_top(int i){while(i)p[i]=top[i],i-=i&-i;}
inline int kth(int l,int r,int k){
	to_top(r),to_top(l-1);
	int lp=0,rp=100000;
	while(lp<rp){
		int v=get_ls(r)-get_ls(l-1),mid=(lp+rp)>>1;
		if(k<=v)to_ls(r),to_ls(l-1),rp=mid;
		else k-=v,to_rs(r),to_rs(l-1),lp=mid+1;
	}
	return lp;
}
inline int read(){
	int r=0,i=getchar();
	while(i<'0'||i>'9')i=getchar();
	while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar();
	return r;
}
void init(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)a[i]=read(),top[i]=p[i]=New(0,100000,0,0);
	for(int i=1;i<=n;i++)update(i,a[i],1);
}
int main(){
	init();
	while(q--){
		char c;cin>>c;
		int x=read(),y=read();
		if(c=='Q')printf("%d\n",kth(x,y,read()));
		else update(x,a[x],-1),a[x]=y,update(x,a[x],1);
	}
	return 0;
}