#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define MN 100010
#define N 4001000
using namespace std;
typedef long long LL;
typedef long double LD;
int ta[MN],op[MN][3],n,m,a[MN];char ops[MN][5];
int mlc[MN],mrc[MN],ml[MN],mr[MN],root[MN];
int lc[N],rc[N],sum[N],l[N],r[N],Len=0,len,mlen,flag[N];
int gp(int x){return lower_bound(ta+1,ta+1+Len,x)-ta;}
int newx(int x)
{flag[++len]=1;lc[len]=lc[x];rc[len]=rc[x];sum[len]=sum[x];l[len]=l[x];r[len]=r[x];return len;}
void upd(int x){sum[x]=sum[lc[x]]+sum[rc[x]];}
void build(int x,int L,int R)
{
  l[x]=L;r[x]=R;int mid=(L+R)>>1;
  if (L==R) return;
  lc[x]=++len;build(lc[x],L,mid);
  rc[x]=++len;build(rc[x],mid+1,R);
}
void mbuild(int x,int L,int R)
{
  ml[x]=L;mr[x]=R;root[x]=newx(1);int mid=(L+R)>>1;
  if (L==R) return;
  mlc[x]=++mlen;mbuild(mlc[x],L,mid);
  mrc[x]=++mlen;mbuild(mrc[x],mid+1,R);
}
void ins(int x,int p,int d)
{
  if (l[x]==r[x]) {sum[x]+=d;return;}
  int mid=(l[x]+r[x])>>1;
  if (p<=mid) 
  {
    if (!flag[lc[x]]) lc[x]=newx(lc[x]);
    ins(lc[x],p,d);
  }else 
  {
    if (!flag[rc[x]]) rc[x]=newx(rc[x]);
    ins(rc[x],p,d);
  }
  upd(x);
}
void mins(int x,int p1,int p2,int d)
{
  ins(root[x],p2,d);
  if (ml[x]==mr[x]) return;
  int mid=(ml[x]+mr[x])>>1;
  if (p1<=mid) mins(mlc[x],p1,p2,d);
  else mins(mrc[x],p1,p2,d);
}
int qu(int x,int L,int R)
{
  if (l[x]==L&&r[x]==R) return sum[x];
  int mid=(l[x]+r[x])>>1;
  if (R<=mid) return qu(lc[x],L,R);
  if (L>mid) return qu(rc[x],L,R);
  return qu(lc[x],L,mid)+qu(rc[x],mid+1,R);
}
int mqu(int x,int L,int R,int kth)
{
  if (ml[x]==mr[x]) return ml[x]; 
  int tmp=qu(root[mlc[x]],L,R);
  if (kth>tmp) return mqu(mrc[x],L,R,kth-tmp);
  return mqu(mlc[x],L,R,kth);
}
int main()
{
  ios::sync_with_stdio(false);
  scanf("%d%d",&n,&m);int i;
  FOR(i,1,n) {scanf("%d",&a[i]);ta[++Len]=a[i];}
  FOR(i,1,m) 
  {
    scanf("%s%d%d",ops[i],&op[i][0],&op[i][1]);
    if (ops[i][0]=='Q') scanf("%d",&op[i][2]);
    else ta[++Len]=op[i][1];
  }
  sort(ta+1,ta+1+Len);
  Len=unique(ta+1,ta+1+Len)-ta-1;
  len=mlen=1;
  build(1,1,n);
  mbuild(1,1,Len);
  FOR(i,1,n) mins(1,gp(a[i]),i,1);
  FOR(i,1,m)
  {
    if (ops[i][0]=='C')
    {
      int p2=op[i][0];
      int p1=gp(a[p2]);mins(1,p1,p2,-1);
      p1=gp(op[i][1]);mins(1,p1,p2,1);
      a[p2]=op[i][1];
    }else
    {
      printf("%d\n",ta[mqu(1,op[i][0],op[i][1],op[i][2])]);
    }
  }
  return 0;
}