#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int Num,CH[12],f,c;

inline void R(int &x){

    c=0;f=1;

    for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

    for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');

    x*=f;

}

inline void P(int x){

    if(x<10)putchar(x+'0');

    else{P(x/10);putchar(x%10+'0');}

}

struct Point{int v,p;}t[20001];

bool operator < (const Point &a,const Point &b){return a.v<b.v;}

int n,m,xs[10001],ys[10001],ks[10001],sum=1,en,en2,ma[20001],l[111],r[111];

int a[20001],num[10001],num2[20001],l2[145];

char op[10001];

struct Val_Block

{

	int b[20001],sumv[145];

	void Insert(const int &x){++b[x]; ++sumv[num2[x]];}

	void Delete(const int &x){--b[x]; --sumv[num2[x]];}

}T[111],S;

int Kth(const int &L,const int &R,const int &x)

{

	int cnt=0,res;

	if(num[L]+1>=num[R])

	  {

	  	for(int i=L;i<=R;++i) S.Insert(a[i]);

	  	for(int i=1;;++i)

          {

            cnt+=S.sumv[i];

            if(cnt>=x)

              {

                cnt-=S.sumv[i];

                for(int j=l2[i];;++j)

                {cnt+=S.b[j]; if(cnt>=x) {res=j; goto OUT2;}}

              }

          } OUT2:

        for(int i=L;i<=R;++i) S.Delete(a[i]);

        return res;

	  }

	for(int i=L;i<=r[num[L]];++i) S.Insert(a[i]);

	for(int i=l[num[R]];i<=R;++i) S.Insert(a[i]);

    int LB=num[L],RB=num[R]-1;

    for(int i=1;;++i)

      {

        cnt+=(T[RB].sumv[i]-T[LB].sumv[i]+S.sumv[i]);

        if(cnt>=x)

          {

            cnt-=(T[RB].sumv[i]-T[LB].sumv[i]+S.sumv[i]);

            for(int j=l2[i];;++j)

            {cnt+=(T[RB].b[j]-T[LB].b[j]+S.b[j]); if(cnt>=x) {res=j; goto OUT;}}

          }

      } OUT:

	for(int i=L;i<=r[num[L]];++i) S.Delete(a[i]);

	for(int i=l[num[R]];i<=R;++i) S.Delete(a[i]);

	return res;

}

void makeblock()

{

	int sz=sqrt(n); if(!sz) sz=1;

	for(;sum*sz<n;++sum)

	  {

	  	l[sum]=r[sum-1]+1; r[sum]=sum*sz;

	  	for(int i=l[sum];i<=r[sum];++i) num[i]=sum;

	  }

	l[sum]=r[sum-1]+1; r[sum]=n;

	for(int i=l[sum];i<=r[sum];++i) num[i]=sum;

}

void val_mb()

{

	int tot=1,sz=sqrt(en2); if(!sz) sz=1;

	for(;tot*sz<en2;++tot)

	  {

	  	l2[tot]=(tot-1)*sz+1;

	  	int R=tot*sz;

	  	for(int i=l2[tot];i<=R;++i) num2[i]=tot;

	  }

	l2[tot]=(tot-1)*sz+1;

	for(int i=l2[tot];i<=en2;++i) num2[i]=tot;

}

void Init_Ts()

{

	for(int i=1;i<=sum;++i)

	  {

	  	T[i]=T[i-1];

	  	for(int j=l[i];j<=r[i];++j) T[i].Insert(a[j]);

	  }

}

int main()

{

	R(n); R(m); en=n; makeblock();

	for(int i=1;i<=n;++i) {R(t[i].v); t[i].p=i;} getchar();

	for(int i=1;i<=m;++i)

	  {

	  	op[i]=getchar(); R(xs[i]); R(ys[i]);

	  	if(op[i]=='Q') R(ks[i]);

	  	else {t[++en].v=ys[i]; t[en].p=en;}

	  }

	sort(t+1,t+en+1);

	ma[a[t[1].p]=++en2]=t[1].v;

    for(int i=2;i<=en;++i)

      {

        if(t[i].v!=t[i-1].v) ++en2;

        ma[a[t[i].p]=en2]=t[i].v;

      }

	val_mb(); Init_Ts(); en=n;

    for(int i=1;i<=m;++i)

      {

      	if(op[i]=='C')

      	  {

      	  	++en;

      	  	for(int j=num[xs[i]];j<=sum;++j)

		      T[j].Delete(a[xs[i]]),T[j].Insert(a[en]);

		    a[xs[i]]=a[en];

      	  }

		else P(ma[Kth(xs[i],ys[i],ks[i])]),puts("");

      }

	return 0;

}