#include<bits/stdc++.h>

#define lowbit(x) x&-x

using namespace std;

typedef long long ll;

const int N=1e6+10;

int n,m;
int arr[N],brr[N],len,tot;
int root[N],lc[N*24],rc[N*24],sum[N*24];
int tmp[2][N*24],cnt0,cnt1;

int read()
{
	char ch=getchar();
	int x=0,f=1;
	while(!isdigit(ch)){
		if(ch=='-') 
		f=-1;
		ch=getchar();
	}
  	while(isdigit(ch)){
  		x=x*10+ch-'0',ch=getchar();
	}
  	return x*f;	
}

struct node
{
	int l,r,k;
}q[N];

int Newnode() {return ++tot;}

int add(int w,int l,int r,int p,int v)
{
	int nd=Newnode();
	sum[nd]=sum[w]+v;
	if(l==r) return nd;
	int mid=l+(r-l)/2;
	if(p<=mid)
	{
		lc[nd]=add(lc[w],l,mid,p,v);
		rc[nd]=rc[w];
	}
	else
	{
		lc[nd]=lc[w];
		rc[nd]=add(rc[w],mid+1,r,p,v);
	}
	return nd;
}

void modify(int x,int y)
{
	for(int i=x;i<=n;i+=lowbit(i)) root[i]=add(root[i],1,len,arr[x],y);
}

int query(int l,int r,int k)
{
	if(l==r) return brr[l];
	int res=0;
	int mid=l+(r-l)/2;
	for(int i=1;i<=cnt1;i++) res+=sum[lc[tmp[1][i]]];
	for(int i=1;i<=cnt0;i++) res-=sum[lc[tmp[0][i]]];
	if(k<=res)
	{
		for(int i=1;i<=cnt1;i++) tmp[1][i]=lc[tmp[1][i]];
		for(int i=1;i<=cnt0;i++) tmp[0][i]=lc[tmp[0][i]];
		return query(l,mid,k);
	}
	else
	{
		for(int i=1;i<=cnt1;i++) tmp[1][i]=rc[tmp[1][i]];
		for(int i=1;i<=cnt0;i++) tmp[0][i]=rc[tmp[0][i]];
		return query(mid+1,r,k-res);	
	}

}

int ask(int l,int r,int k)
{
	memset(tmp,0,sizeof tmp);
	cnt0=cnt1=0;
	for(int i=l;i;i-=lowbit(i)) tmp[0][++cnt0]=root[i];
	for(int i=r;i;i-=lowbit(i)) tmp[1][++cnt1]=root[i];
	return query(1,len,k);
}

int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		arr[i]=read();
		brr[i]=arr[i];
	}
	int cnt=n;
	for(int i=1;i<=m;i++)
	{
		char opt;cin>>opt;
		if(opt=='Q')
		{
			int l,r,k;
			l=read();r=read();k=read();
			q[i]=(node){l,r,k};
		}
		else
		{
			int x,y;
			x=read();y=read(); 
			q[i]=(node){x,y,0};
			brr[++cnt]=y;
		}
	}
	sort(brr+1,brr+cnt+1);
	len=unique(brr+1,brr+cnt+1)-brr-1;
	for(int i=1;i<=n;i++) arr[i]=lower_bound(brr+1,brr+len+1,arr[i])-brr;
	for(int i=1;i<=n;i++) modify(i,1);
	for(int i=1;i<=m;i++)
	{
		if(q[i].k) printf("%d\n",ask(q[i].l-1,q[i].r,q[i].k));
		else
		{
			q[i].r=lower_bound(brr+1,brr+len+1,q[i].r)-brr;
			modify(q[i].l,-1);
			arr[q[i].l]=q[i].r;
			modify(q[i].l,1);
		}
//		for(int j=1;j<=n;j++) cout<<arr[j]<<" ";
//		cout<<endl;
	}
	return 0;
}