#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

using namespace std;

int a[];

struct node

{

    int lc,rc,c;

}tr[];int cnt;

int rt[];int n;

int ust[];//树状数组

int lowbit(int x)//树状数组用来找上司或下属

{

    return x&-x;

}

void Link(int &u,int l,int r,int p,int c)

{

    if(u==) u=++cnt;

    tr[u].c+=c;

    if(l==r) return ;

    int mid=(l+r)/;

    if(p<=mid) Link(tr[u].lc,l,mid,p,c);

    else Link(tr[u].rc,mid+,r,p,c);

}

void Merge(int &u1,int u2)

{

    if(u1==){u1=u2;return ;}

    if(u2==) return ;

    tr[u1].c+=tr[u2].c;

    Merge(tr[u1].lc,tr[u2].lc);

    Merge(tr[u1].rc,tr[u2].rc);

}

void Turn(int u,int c)//树状数组的实时更新

//c==-1时树状数组记录每个点所在线段树的根

//c==0时记录左孩子

//c==1时记录右孩子

{

    while(u>=n+)

    {

        if(c==-) ust[u]=rt[u];

        else if(c==) ust[u]=tr[ust[u]].lc;

        else if(c==) ust[u]=tr[ust[u]].rc;

        u-=lowbit(u);

    }

}

void Modefy(int u,int p,int c)//对于修改值就用树状数组来节约时间

{

    while(u<=*n)

    {

        Link(rt[u],,,p,c);

        u+=lowbit(u);

    }

}

int Getsum(int u)//求出修改过后树状数组得到的值

{

    int ret=;

    while(u>=n+)

    {

        ret+=tr[tr[ust[u]].lc].c;

        u-=lowbit(u);

    }

    return ret;

}

int Ask(int u1,int u2,int p1,int p2,int l,int r,int p)

{

    if(l==r) return l;

    int c=tr[tr[u2].lc].c-tr[tr[u1].lc].c+Getsum(p2+n)-Getsum(p1+n);

    int mid=(l+r)/;

    if(p<=c)

    {

        Turn(p1+n,);

        Turn(p2+n,);

        return Ask(tr[u1].lc,tr[u2].lc,p1,p2,l,mid,p);

    }

    else

    {

        Turn(p1+n,);

        Turn(p2+n,);

        return Ask(tr[u1].rc,tr[u2].rc,p1,p2,mid+,r,p-c);

    }

}

int main()

{

    int m;

    scanf("%d%d",&n,&m);

    cnt=;memset(rt,,sizeof(rt));

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

    {

        scanf("%d",&a[i]);

        Link(rt[i],,,a[i],);

        Merge(rt[i],rt[i-]);

    }

    char st[];

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

    {

        scanf("%s",st+);

        if(st[]=='Q')

        {

            int l,r,k;

            scanf("%d%d%d",&l,&r,&k);

            Turn(l+n-,-);

            Turn(r+n,-);

            printf("%d\n",Ask(rt[l-],rt[r],l-,r,,,k));

        }

        else

        {

            int p,c;

            scanf("%d%d",&p,&c);

            Modefy(p+n,a[p],-);

            a[p]=c;

            Modefy(p+n,a[p],);

        }

    }

    return ;

}