RT，P2617

#include<bits/stdc++.h>

#define  lb(x)  (x&-x)

using std::vector;

int n,m;
int cnt=0;
int s[100005],r[100005];
class Q{
public:
    char c;
    int i,j,k;
}q[100005];

class Node{
public:
    Node* l,* r;
    int size;
    Node(){
        l=r=0;
        size=0;
    }
};
Node* t[200005];
void change(vector<Node*> a,int L,int R,int k,int num){
    for(Node* &x:a){
        if(x->l==0)x->l=new Node;
        if(x->r==0)x->r=new Node;
    }
    for(Node* &x:a)x->size+=num;
    if(L==R)return;
    int M=(L+R)/2;
    if(k<=M){
        for(Node* &x:a)x=x->l;
        change(a,L,M,k,num);
    }else{
        for(Node* &x:a)x=x->r;
        change(a,M+1,R,k,num);
    }
}
void change(int x,int y,bool insing=0){
    vector<Node*> a;
    int X=x;
    for(;x<=cnt;x+=lb(x)){
        if(t[x]==0)t[x]=new Node;
        a.push_back(t[x]);
    }
    change(a,0,cnt,s[X],-1);
    change(a,0,cnt,y,insing+1);
    s[X]=y;
}
int rank(vector<Node*> a,vector<Node*> b,int L,int R,int k){
    for(Node* &x:a){
        if(x->l==0)x->l=new Node;
        if(x->r==0)x->r=new Node;
    }
    for(Node* &x:b){
        if(x->l==0)x->l=new Node;
        if(x->r==0)x->r=new Node;
    }
    if(L==R){
        return L|R;
    }
    int M=(L+R)/2;
    int lsize=0;
    for(Node* &x:a)lsize+=x->l->size;
    for(Node* &x:b)lsize-=x->l->size;
    if(lsize>=k){
        for(Node* &x:a)x=x->l;
        for(Node* &x:b)x=x->l;
        return rank(a,b,L,M,k);
    }else{
        for(Node* &x:a)x=x->r;
        for(Node* &x:b)x=x->r;
        return rank(a,b,M+1,R,k-lsize);
    }
}
int rank(int x,int y,int k){
    vector<Node*> a,b;
    for(;x;x-=lb(x)){
        if(t[x]==0)t[x]=new Node;
        a.push_back(t[x]);
    }
    for(--y;y;y-=lb(y)){
        if(t[y]==0)t[y]=new Node;
        b.push_back(t[y]);
    }
    return rank(a,b,0,cnt,k);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&s[i]);
        r[++cnt]=s[i];
    }
    for(int i=1;i<=m;++i){
        std::cin>>q[i].c;
        if(q[i].c=='Q'){
            scanf("%d%d%d",&q[i].j,&q[i].i,&q[i].k);
        }else{
            scanf("%d%d",&q[i].i,&q[i].j);
            r[++cnt]=q[i].j;
        }
    }
    std::sort(r+1,r+1+cnt);
    cnt=std::unique(r+1,r+1+cnt)-r;
    
    for(int i=1;i<=n;++i){
        s[i]=std::lower_bound(r+1,r+1+cnt,s[i])-r;
        change(i,s[i],1);
    }
    for(int i=1;i<=m;++i){
        if(q[i].c=='Q'){
            printf("%d\n",r[rank(q[i].i,q[i].j,q[i].k)]);
        }else{
            q[i].j=std::lower_bound(r+1,r+1+cnt,q[i].j)-r;
            change(q[i].i,q[i].j);
        }
    }
    
    return 0;
}