#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,m;
int L[N],R[N],sum[N],rt[N],tot;
int change(int p,int l,int r,int pos,int v)
{
	int rt=++tot;
	L[rt]=L[p];
	R[rt]=R[p];
	sum[rt]=sum[p]+v;
	if(l==r)return rt;
	int mid=(l+r)>>1;
	if(pos<=mid)
	L[rt]=change(L[rt],l,mid,pos,v);
	else
	R[rt]=change(R[rt],mid+1,r,pos,v);
	return rt;
}
int xx[N],yy[N],totx,toty;
int lowit(int x)
{
	return x&(-x);
}
int query(int l,int r,int k)
{
	if(l==r)return l;
	int num=0;
	int mid=(l+r)>>1;
	for(int i=1;i<=totx;i++)
	num-=sum[L[xx[i]]];
	for(int i=1;i<=toty;i++)
	num+=sum[L[yy[i]]];
	if(k<=num)
	{
		for(int i=1;i<=totx;i++)
		xx[i]=L[xx[i]];
		for(int i=1;i<=toty;i++)
		yy[i]=L[yy[i]];
		return query(l,mid,k);
	}
	else
	{
		for(int i=1;i<=totx;i++)
		xx[i]=R[xx[i]];
		for(int i=1;i<=toty;i++)
		yy[i]=R[yy[i]];
		return query(mid+1,r,k-num);
	} 
}
int a[N],b[N],totn;
void add(int x,int v)
{
	int k=lower_bound(b+1,b+1+totn,a[x])-b;
	for(int i=x;i<=n;i+=lowit(i))
	rt[i]=change(rt[i],1,totn,k,v);
}
char s[20],ca[N],cb[N],cc[N];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	totn=n;
	for(int i=1;i<=m;i++)
	{
		cin>>s;
		cin>>ca[i]>>cb[i];
		if(s[0]=='Q')
		{
			cin>>cc[i];
		}
		else
		b[++totn]=cb[i];
	}
	sort(b+1,b+1+totn);
	totn=unique(b+1,b+1+totn)-b-1;
	for(int i=1;i<=n;i++)
	add(i,1);
	for(int i=1;i<=m;i++)
	{
		if(cc[i])
		{
			totx=toty=0;
			for(int j=ca[i]-1;j;j-=lowit(j))
			xx[++totx]=rt[j];
			for(int j=cb[i];j;j-=lowit(j))
			yy[++toty]=rt[j];
			cout<<b[query(1,totn,cc[i])]<<endl;
		}
		else
		{
			add(ca[i],-1);
			a[ca[i]]=cb[i];
			add(ca[i],1);
		}
	}
}