#include<bits/stdc++.h>
using namespace std;
struct node
{
	int v,k,l,r,s;
};
node tree[4000005];
int a[1000005];
int n,m;
int tot=0;
struct FHQ
{
	int root,l,r;
	int newnode(int v)
	{
		tree[++tot].v=v;
		tree[tot].k=rand();
		tree[tot].s=1;
		return tot;
	}
	void pushup(int p)
	{
		tree[p].s=tree[tree[p].l].s+tree[tree[p].r].s+1;
	}
	void split(int p,int v,int &x,int &y)
	{
		if (p==0)
		{
			x=0,y=0;
			return;
		}
		if (tree[p].v<=v)
		{
			x=p;
			split(tree[p].r,v,tree[p].r,y);
		}
		else
		{
			y=p;
			split(tree[p].l,v,x,tree[p].l);
		}
		pushup(p);
	}
	int merge(int x,int y)
	{
		if (!x || !y)
			return x+y;
		if (tree[x].k<tree[y].k)
		{
			tree[x].r=merge(tree[x].r,y);
			pushup(x);
			return x;
		}
		else
		{
			tree[y].l=merge(x,tree[y].l);
			pushup(y);
			return y;
		}
	}
	void ins(int v)
	{
		int x,y,z;
		split(root,v,x,y);
		z=newnode(v);
		root=merge(merge(x,z),y);
	}
	void del(int v)
	{
		int x,y,z;
		split(root,v,x,z);
		split(x,v-1,x,y);
		y=merge(tree[y].l,tree[y].r);
		root=merge(merge(x,y),z);
	}
	int get_k(int p,int k)
	{
		if (k<=tree[tree[p].l].s)
			return get_k(tree[p].l,k);
		if (k==tree[tree[p].l].s+1)
			return p;
		return get_k(tree[p].r,k-tree[tree[p].l].s-1);
	}
	int get_p(int v)
	{
		int x,y,ans;
		split(root,v-1,x,y);
		ans=tree[x].s+1;
		root=merge(x,y);
		return ans;
	}
	int get_s(int v)
	{
		int k,ans;
		k=get_k(root,v);
		ans=tree[k].v;
		return ans;
	}
	void build(int l,int r)
	{
		for (int i=l;i<=r;i++)
			ins(a[i]);
	}
};
FHQ treap[1000005];
void build(int k,int l,int r)
{
	treap[k].build(l,r);
	treap[k].l=l;
	treap[k].r=r;
	if (l==r)
		return;
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
}
int query_p(int k,int x,int y,int z)
{
	if (treap[k].l>=x && treap[k].r<=y)
		return treap[k].get_p(z)-1;
	int mid=(treap[k].l+treap[k].r)/2;
	int ans=0;
	if (x<=mid)
		ans+=query_p(k*2,x,y,z);
	if (y>mid)
		ans+=query_p(k*2+1,x,y,z);
	return ans;
}
int query_s(int k,int x,int y,int z)
{
	int l=1,r=1e8,mid,ans;
	while (l<=r)
	{
		mid=(l+r)/2;
		int p=query_p(1,x,y,mid)+1;
		if (p<=z)
		{
			ans=mid;
			l=mid+1;
		}
		else
			r=mid-1;
	}
	return ans;
}
void update(int k,int x,int y)
{
	treap[k].del(a[x]);
	treap[k].ins(y);
	if (treap[k].l==treap[k].r)
		return;
	int mid=(treap[k].l+treap[k].r)/2;
	if (x<=mid)
		update(k*2,x,y);
	else
		update(k*2+1,x,y);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(0));
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	while (m--)
	{
		char o;
		int x,y,z;
		cin>>o;
		if (o=='Q')
		{
			cin>>x>>y>>z;
			cout<<query_s(1,x,y,z)<<'\n';
		}
		else if (o=='C')
		{
			cin>>x>>y;
			update(1,x,y);
			a[x]=y;
		}
	}
	return 0;
}