#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=1e5+100; 
int n,m,xa[N],k,ans[N],inx,iny,ink,tr[N];
char ch;
struct node
{
	int val,x,y,fh,op,id;//op=1:单点加 op=2:查询 
}a[N*3],b1[N*3],b2[N*3];
int lowbit(int num)
{
	return num&(-num);
}
void add(int p,int num)
{
	for(int i=p;i<=n;i+=lowbit(i)) tr[i]+=num;
}
int sum(int p)
{
	int s=0;
	for(int i=p;i;i-=lowbit(i)) s+=tr[i];
	return s;
}
int query(int l,int r)
{
	return sum(r)-sum(l-1);
} 
void whole_binary_find(int l,int r,int ql,int qr)
{
	//cout<<l<<" "<<r<<" "<<ql<<" "<<qr<<"\n";
	if(ql>qr) return;
	if(l==r)
	{
		for(int i=ql;i<=qr;i++)
		{
			if(a[i].op==2) ans[a[i].id]=l;
		}
		return;
	}
	int k1=0,k2=0,cnt,mid=(l+r)>>1;
	for(int i=ql;i<=qr;i++)
	{
		if(a[i].op==1)
		{
			if(a[i].y<=mid)
			{
				add(a[i].x,a[i].fh);
				b1[++k1]=a[i];
			}
			else b2[++k2]=a[i];
		}
		else
		{
			cnt=query(a[i].x,a[i].y);
			if(cnt>=a[i].val) b1[++k1]=a[i];
			else b2[++k2]=a[i];
		}
	}
	for(int i=1;i<=k1;i++)
	{
		if(b1[i].op==1) add(b1[i].x,-b1[i].fh);
	}
	for(int i=ql,j=1;j<=k1;i++,j++) a[i]=b1[j];
	for(int i=ql+k1,j=1;j<=k2;i++,j++) a[i]=b2[j];
	whole_binary_find(l,mid,ql,ql+k1-1);
	whole_binary_find(mid+1,r,ql+k1,qr); 
}
int main()
{
	/*ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);*/
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>xa[i];
		a[++k].op=1,a[k].x=i,a[k].y=xa[i];
	}
	for(int i=1;i<=m;i++)
	{
		ans[i]=-1;
		cin>>ch>>inx>>iny;
		if(ch=='Q') 
		{
			cin>>ink;
			a[++k].id=i,a[k].op=2,a[k].x=inx,a[k].y=iny,a[k].val=ink;
		}
		else 
		{
			a[++k].op=1,a[k].x=inx,a[k].y=xa[inx],a[k].fh=-1,xa[inx]=iny;
			a[++k].op=1,a[k].x=inx,a[k].y=iny,a[k].fh=1;
		}
	}
	whole_binary_find(0,1e9,1,k);
	for(int i=1;i<=m;i++)
	{
		if(ans[i]!=-1) cout<<ans[i]<<"\n";
	} 
	return 0;
}