#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
/*线段树节点,要存放左右儿子编号,区间内元素个数*/
struct SegmentTree {
    int ls,rs,sum;
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define sum(x) tr[x].sum
} tr[N*400]; //动态开点，相对需要的空间少一点
/*因为要离散化,所以要提前读取所有操作*/
struct Query {
    int l,r,k;//查询操作,询问区间[l,r]内第k大数的值
    int p,x; //修改操作,修改位置p位置上的元素为x
} qy[N];
int sz = N;/*不同版本的线段树总数,即动态申请节点编号,初始值要为N,因为前n个节点被使用*/
int a[N],n,m,tot = 0;//tot离散化用
char op[10];
void Insert(int rt,int l,int r,int p,int d) {   /*对以rt为根的线段树,区间[l,r]内新增一个元素x*/
    sum(rt) += d;
    if(l == r) return;
    int mid = l+r>>1;
    if(p <= mid) {
        if(!ls(rt)) ls(rt) = ++sz;//如果该子树没有子节点则新建，动态开点 
        Insert(ls(rt),l,mid,p,d);
    } else {
        if(!rs(rt)) rs(rt) = ++sz;////如果该子树没有子节点则新建，动态开点 
        Insert(rs(rt),mid+1,r,p,d);
    }
}
void add(int l,int p,int d) {/*向树状数组中的 线段树中 位置p值+d,要从l开始*/
    for(int x = l; x <= n; x += x&-x)
        Insert(x,1,tot,p,d);
}
int t1[N],t2[N],c1,c2;//临时记录遍历路径
int ask(int l,int r,int k) {/*返回区间[l,r]内第k大元素的值(离散化后的)*/
    if(l == r) return l;
    int res = 0, mid = l+r>>1;
    for(int i = 1; i <= c2; i++) res += sum(ls(t2[i]));//tr[tr[t2[i].ls]].sum 
    for(int i = 1; i <= c1; i++) res -= sum(ls(t1[i]));
    if(res >= k) {
        for(int i = 1; i <= c1; i++) t1[i] = ls(t1[i]);//把左孩子作为新的根结点 
        for(int i = 1; i <= c2; i++) t2[i] = ls(t2[i]);
        return ask(l,mid,k);
    } else {
        for(int i = 1; i <= c1; i++) t1[i] = rs(t1[i]);
        for(int i = 1; i <= c2; i++) t2[i] = rs(t2[i]);
        return ask(mid+1,r,k-res);
    }
}
int tmp[N*2];//离散化用
int query(int l,int r,int k) {
    c1 = c2 = 0;/*我们将树状数组上待查询的线段树的根节点编号先存储*/
    for(int i = l; i; i -= i&-i) t1[++c1] = i;
    for(int i = r; i; i -= i&-i) t2[++c2] = i;
    int x = ask(1,tot,k);   //注意查询区间是[1,tot]
    return tmp[x];
}
int main() {
    scanf("%d%d",&n,&m);//n个数 m次操作
    for(int i = 1; i <= n; i++) scanf("%d",a+i),tmp[++tot] = a[i];//数组中原有数据
    for(int i = 1; i <= m; i++) {
        scanf("%s",op);
        if(op[0] == 'C') {//修改
            scanf("%d%d",&qy[i].p,&qy[i].x);
            tmp[++tot] = qy[i].x;//后来修改的数字也要先存储,方便离散化
        } else scanf("%d%d%d",&qy[i].l,&qy[i].r,&qy[i].k);
    }
    //离散化
    sort(tmp+1,tmp+1+tot);//排序
    tot = unique(tmp+1,tmp+1+tot)-tmp-1;//去重
    for(int i = 1; i <= n; i++) {
        int p = lower_bound(tmp+1,tmp+1+tot,a[i])-tmp;
        add(i,p,1);
    }
    for(int i = 1; i <= m; i++) {
        if(qy[i].l) {//查询
            int l = qy[i].l, r = qy[i].r;
            printf("%d\n",query(l-1,r,qy[i].k));
        } else {
            int pre = lower_bound(tmp+1,tmp+1+tot,a[qy[i].p])-tmp;
            int p = lower_bound(tmp+1,tmp+1+tot,qy[i].x)-tmp;
            add(qy[i].p,pre,-1);//pre位置上的这个数字要去掉1个
            add(qy[i].p,p,1);//p位置上新增一个数字
            a[qy[i].p] = qy[i].x;//要将修改后的位置重新赋新值
        }
    }
    return 0;
}
/*
树状数组套线段树的写法
在树状数组每一个C[i]的位置都是一棵线段树
当所有n个数据都增加到树状数组中以后，
每棵C[i]位置的线段树就相当于是加入第i个数据时的一个历史版本
注意：
1、一定要把修改后的数据提前也加入到需要离散化的数组中，这个处理相当于
是给线段树预留叶子结点的空间。
例如有4个数据： 20 5 7 49 然后计划把5改为10
如果一开始没有把10和原数组中4个数放在一起做离散化处理，
那么20就是离散化后的数组中的第3名；
如果把10放进去一起离散化，就会发现其实10是第3名，20是第4名
所以如果没有把10放进去就会造成后面把5修改成10时，10在线段树上找不到对应的结点。
当然如果没有离散化，其实就不需要这样处理了。

2、要深刻理解 add(i, p, 1)的操作： 
add(i, p, 1)的操作其实就是树状数组的add操作，
但是在这里，每一个树状数组上的C[i]其实都是一棵线段树。
所以add操作其实是就从i位置开始的一系列线段树上找到数字p所属的叶子结点位置。
然后对所有从根到叶子的路径上的所有结点都加1。
 
线段树上每个叶子结点都表示1——tot中的某个数值，
但要注意这个数值是隐含的，并不是叶子结点的编号，也不是叶子结点的sum值
而是通过在线段树树上不断的二分查找最后走到的叶子结点就是要找的那个p值所在的叶子结点。 

*/