#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int size,lt,rt;}tree[maxn*];

int n,m,tot,sz,cnt1,cnt2,N;

int t1[maxn],t2[maxn],a[maxn],b[maxn],x[maxn],y[maxn],z[maxn],root[maxn];

bool q[maxn];

char s[];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int lowbit(int x){return x&-x;}

void update(int &x,int l,int r,int cx,int delta)

{

    tree[++sz]=tree[x];tree[sz].size+=delta;x=sz;

    if(l==r)return;

    int mid=(l+r)>>;

    if(cx<=mid)update(tree[x].lt,l,mid,cx,delta);

    else update(tree[x].rt,mid+,r,cx,delta);

}

int query(int l,int r,int k)

{

    if(l==r)return l;

    int mid=(l+r)>>,sum1=,sum2=;

    for(int i=;i<=cnt1;i++)sum1+=tree[tree[t1[i]].lt].size;

    for(int i=;i<=cnt2;i++)sum2+=tree[tree[t2[i]].lt].size;

    if(sum2-sum1>=k)

    {

        for(int i=;i<=cnt1;i++)t1[i]=tree[t1[i]].lt;

        for(int i=;i<=cnt2;i++)t2[i]=tree[t2[i]].lt;

        return query(l,mid,k);

    }

    for(int i=;i<=cnt1;i++)t1[i]=tree[t1[i]].rt;

    for(int i=;i<=cnt2;i++)t2[i]=tree[t2[i]].rt;

    return query(mid+,r,k-(sum2-sum1));

}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)read(a[i]),b[++N]=a[i];

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

    {

        scanf("%s",s+);

        read(x[i]);read(y[i]);

        if(s[]=='Q')read(z[i]),q[i]=;

        else b[++N]=y[i];

    }

    sort(b+,b++N);N=unique(b+,b++N)-b-;

    for(int i=;i<=n;i++)a[i]=lower_bound(b+,b++N,a[i])-b;

    for(int i=;i<=n;i++)

    for(int j=i;j<=n;j+=lowbit(j))

    update(root[j],,N,a[i],);

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

    if(q[i])

    {

        cnt1=cnt2=;

        for(int j=x[i]-;j;j-=lowbit(j))

        t1[++cnt1]=root[j];

        for(int j=y[i];j;j-=lowbit(j))

        t2[++cnt2]=root[j];

        printf("%d\n",b[query(,N,z[i])]);

    }

    else

    {

        for(int j=x[i];j<=n;j+=lowbit(j))

        update(root[j],,N,a[x[i]],-);

        a[x[i]]=lower_bound(b+,b++N,y[i])-b;;

        for(int j=x[i];j<=n;j+=lowbit(j))

        update(root[j],,N,a[x[i]],);

    }

    return ;

}