#include <bits/stdc++.h>

using namespace std;

const int N=5e6+110;
int n,m;

struct node{
	int l,r;
	int val,key;
	int sz;
}t[N];

int idx,root[N];
mt19937 rnd;

int newnode(int x){
	t[++idx].val=x;
	t[idx].key=rnd();
	t[idx].sz=1;
	return idx;
}
void push(int p){
	t[p].sz=t[t[p].l].sz+t[t[p].r].sz+1;
}

void split(int p,int x,int &A,int &B){
	if(!p){
		A=B=0;
		return ;
	}
	if(t[p].val<=x)A=p,split(t[p].r,x,t[p].r,B);
	else B=p,split(t[p].l,x,A,t[p].l);
	push(p);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(t[x].key<t[y].key){
		t[x].r=merge(t[x].r,y);
		push(x);
		return x;
	}
	else{
		t[y].l=merge(x,t[y].l);
		push(y);
		return y;
	}
}

struct LineTree{
	int l,r;
}a[N]; 
int bas[N];

void add(int p,int x){
	int a,b,c;
	split(root[p],x,a,b);
	c=newnode(x);
	root[p]=merge(merge(a,c),b);
} 
void del(int p,int x){
	int a,b,c;
	split(root[p],x,a,b);
	split(a,x-1,a,c);
	c=merge(t[c].l,t[c].r);
	root[p]=merge(merge(a,c),b);
}
int kso(int p,int x){
	int a,b;
	split(root[p],x-1,a,b);
	int kk=t[a].sz+1;
	root[p]=merge(a,b);
	return kk; 
}

void buildtree(int p,int l,int r){
	a[p].l=l;
	a[p].r=r;
	for(int i=l;i<=r;i++){
		add(p,bas[i]);
	}
	if(l==r)return ;
	buildtree(p<<1,l,(l+r)>>1);
	buildtree(p<<1|1,((l+r)>>1)+1,r);
}
int kso_(int p,int l,int r,int x){
	if(a[p].l>=l&&a[p].r<=r){
		return kso(p,x)-1;
	}
	int kk=0;
	if((a[p].l+a[p].r)>>1>=l)kk+=kso_(p<<1,l,r,x);
	if(((a[p].l+a[p].r)>>1)+1<=r)kk+=kso_(p<<1|1,l,r,x);
	return kk;
}
int kth_(int l,int r,int x){
	int L=0,R=1e8;
	int ans=0;
	while(L<R){
		int mid=(L+R+1)>>1;
		if(kso_(1,l,r,mid)+1<=x){
			L=mid;
		}
		else R=mid-1;
	}
	return L;
}
void add_(int p,int l,int x){
	del(p,bas[l]);
	add(p,x);
	if(a[p].l==a[p].r)return ;
    (a[p].l+a[p].r)>>1>=l?add_(p<<1,l,x):add_(p<<1|1,l,x);
}

int main(){
    
	srand(time(NULL));
	rnd.seed(rand()^time(NULL));

	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>bas[i];
	}
	buildtree(1,1,n);
	
	while(m--){
        char c;
		int opt,l,r,x;
		cin>>c>>l>>r;
        c=='Q'?opt=2:opt=3;
		if(opt==2){
			cin>>x;
			printf("%d\n",kth_(l,r,x));
		}
		if(opt==3){
			add_(1,l,r);
			bas[l]=r; 
		}
	}
	return 0;
}