#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int MAXN = 1e5 + 5;
int n,m,a[MAXN],tot,dsc[MAXN << 1];
int rec[40][2],num[2];
char opt;
inline int find(int x)
{return lower_bound(dsc + 1,dsc + tot + 1,x) - dsc;}
struct Option
{
    bool opt;
    int l,r,k;
    int x,y;
}q[MAXN];
namespace ChairmanTree
{
    struct Nahida
    {
        int ls,rs,val;
    }tree[MAXN * 120];
    #define lson(rt) tree[rt].ls
    #define rson(rt) tree[rt].rs
    int root[MAXN],cnt;
    inline int copyNode(int rt)
    {
        ++cnt;
        tree[cnt] = tree[rt];
        return cnt;
    }
    inline int Modify(int rt,int l,int r,int val,int delta)
    {
        rt = copyNode(rt);
        tree[rt].val += delta;
        if(l < r)
        {
            int mid = (l + r) >> 1;
            if(val <= mid)
                lson(rt) = Modify(lson(rt),l,mid,val,delta);
            else
                rson(rt) = Modify(rson(rt),mid + 1,r,val,delta);
        }
        return rt;
    }
    inline int queryKth(int l,int r,int k)
    {
        if(l == r)
            return l;
        int x = 0,mid = (l + r) >> 1;
        for(int i = 1;i <= num[0];i++)
            x += tree[lson(rec[i][0])].val;
        for(int i = 1;i <= num[1];i++)
            x -= tree[lson(rec[i][1])].val;
        if(k <= x)
        {
            for(int i = 1;i <= num[0];i++)
                rec[i][0] = lson(rec[i][0]);
            for(int i = 1;i <= num[1];i++)
                rec[i][1] = lson(rec[i][1]);
            return queryKth(l,mid,k);
        }
        else
        {
            for(int i = 1;i <= num[0];i++)
                rec[i][0] = rson(rec[i][0]);
            for(int i = 1;i <= num[1];i++)
                rec[i][1] = rson(rec[i][1]);
            return queryKth(mid + 1,r,k - x);
        }
    }
}
using namespace ChairmanTree;
#define lowbit(x) (x & -x)
namespace BIT
{
    inline void modify(int p,int delta)
    {
        int P = find(a[p]);
        for(int i = p;i <= n;i += lowbit(i))
            root[i] = Modify(root[i],1,tot,P,delta);
    }
    inline int query(int l,int r,int k)
    {
        num[0] = num[1] = 0;
        memset(rec,0,sizeof(rec));
        for(int i = r;i;i -= lowbit(i))
        {
            ++num[0];
            rec[num[0]][0] = root[i];
        }
        for(int i = l - 1;i;i -= lowbit(i))
        {
            ++num[1];
            rec[num[1]][1] = root[i];
        }
        cout << "\n";
        return queryKth(1,tot,k);
    }
}
using namespace BIT;
signed main()
{
    freopen("P2617.in","r",stdin);
    freopen("ans.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        dsc[++tot] = a[i];
    }
    for(int i = 1;i <= m;i++)
    {
        cin >> opt;
        q[i].opt = (opt == 'Q');
        if(q[i].opt)
        {
            cin >> q[i].l >> q[i].r >> q[i].k;
            if(q[i].l > q[i].r)
                swap(q[i].l,q[i].r);
        }
        else
        {
            cin >> q[i].x >> q[i].y;
            dsc[++tot] = q[i].y;
        }
    }
    sort(dsc + 1,dsc + tot + 1);
    tot = unique(dsc + 1,dsc + tot + 1) - dsc - 1;
    for(int i = 1;i <= n;i++)
        modify(i,1);
    for(int i = 1;i <= m;i++)
    {
        if(q[i].opt)
            cout << dsc[query(q[i].l,q[i].r,q[i].k)] << "\n";
        else
        {
            modify(q[i].x,-1);
            a[q[i].x] = q[i].y;
            modify(q[i].x,1);
        }
    }
}

RE，用 gdb 看的原因是 rec 数组里面有负数，但自己不知道哪里错了