#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int n,m,T,a[100005],c[100005],lisan[300005],ans[100005],cnt;
map<int,int>mp;
void add(int x,int y)
{
	for(;x<=n;x+=x&-x)
		c[x]+=y;
}
int ask(int x)
{
	int ans=0;
	for(;x;x-=x&-x)
		ans+=c[x];
	return ans;
}
struct askx
{
	int id,op,l,r,k;
}q[300005],lq[200005],rq[200005];
void solve(int lx,int rx,int s,int t)
{
	if(s>t)
		return;
	if(lx==rx)
	{
		for(int i=s;i<=t;i++)
		{
			if(q[i].op==0)
				ans[q[i].id]=lx;
		}
		return;
	}
	int lt=0,rt=0;
	int mid=(lx+rx)>>1;
	for(int i=s;i<=t;i++)
	{
		if(q[i].op!=0)
		{
			if(q[i].k<=mid)
			{
				add(q[i].l,q[i].op);
				lq[++lt]=q[i];
			}
			else
				rq[++rt]=q[i];
		}
		else
		{
			int cnt=ask(q[i].r)-ask(q[i].l-1);
			if(cnt>=q[i].k)
				lq[++lt]=q[i];
			else
			{
				q[i].k-=cnt;
				rq[++rt]=q[i];
			}
		}
	}
	for(int i=t;i>=s;i--)
	{
		if(q[i].op!=0&&q[i].k<=mid)
			add(q[i].l,-q[i].op);
	}
	for(int i=1;i<=lt;i++)
		q[s+i-1]=lq[i];
	for(int i=1;i<=rt;i++)
		q[s+lt-1+i]=rq[i];
	solve(lx,mid,s,s+lt-1);
	solve(mid+1,rx,s+lt,t);
}
int main()
{
	memset(ans,-1,sizeof(ans));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		q[++T]={i,1,i,i,a[i]};
		lisan[++cnt]=a[i];
	}
	for(int i=1;i<=m;i++)
	{
		char c;
		cin>>c;
		if(c=='Q')
		{
			int l,r,k;
			cin>>l>>r>>k;
			q[++T]={i,0,l,r,k};
		}
		else
		{
			int x,y;
			cin>>x>>y;
			q[++T]={i,-1,x,x,a[x]};
			lisan[++cnt]=a[x];
			q[++T]={i,1,x,x,y};
			lisan[++cnt]=y;
			a[x]=y;
		}
	}
	sort(lisan+1,lisan+cnt+1);
	cnt=unique(lisan+1,lisan+cnt+1)-(lisan+1);
	for(int i=1;i<=cnt;i++)
	{
		if(q[i].op!=0)
		{
			int x=lower_bound(lisan+1,lisan+cnt+1,q[i].k)-lisan;
			if(mp.find(x)==mp.end())
				mp[x]=q[i].k;			
			q[i].k=x;		
		}	
	}
	solve(1,cnt,1,T);
	for(int i=1;i<=m;i++)
	{
		if(ans[i]!=-1)
			cout<<mp[ans[i]]<<"\n";
	}
	return 0;
}