#include<iostream>
#include<algorithm>
const int sz = 1e5 + 10;
int n, q, arr[sz << 1], carr[sz << 1], xpp;
struct query {
    char op;
    int a, b, c = 0;
} que[sz];
struct SegT {
    struct node {
        int lson, rson, val;
    } tree[sz << 9];
    int num;
    void add(int &p, int ln, int rn, int pos, int val) {
        if (p == 0) p = ++num;
        if (ln == rn) return tree[p].val += val, void();
        int mid = ln + rn >> 1;
        if (pos <= mid) add(tree[p].lson, ln, mid, pos, val);
        else add(tree[p].rson, mid + 1, rn, pos, val);
        tree[p].val = tree[tree[p].lson].val + tree[tree[p].rson].val;
    }
    int query(int p, int ln, int rn, int l, int r) {
        if (ln >= l && rn <= r) return tree[p].val;
        int mid = ln + rn >> 1, res = 0;
        if (l <= mid) res += query(tree[p].lson, ln, mid, l, r);
        if (r > mid) res += query(tree[p].rson, mid + 1, rn, l, r);
        return res;
    }
} segt;
struct ST {
    int root[sz << 2];
    void add(int p, int ln, int rn, int pos, int pt, int val) {
        segt.add(root[p], 1, n, pt, val);
        if (ln == rn) return;
        int mid = ln + rn >> 1;
        if (pos <= mid) add(p << 1, ln, mid, pos, pt, val);
        else add(p << 1 | 1, mid + 1, rn, pos, pt, val);
    }
    int query(int p, int ln, int rn, int l, int r, int k) {
        if (ln == rn) return ln;
        int mid = ln + rn >> 1;
        int lsz = segt.query(root[p << 1], 1, n, l, r);
        if (lsz >= k) return query(p << 1, ln, mid, l, r, k);
        else return query(p << 1 | 1, mid + 1, rn, l, r, k - lsz);
    }
} st;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> q, xpp = n;
    for (int i = 1; i <= n; i++) std::cin >> arr[i];
    for (int i = 1; i <= q; i++) {
        std::cin >> que[i].op >> que[i].a >> que[i].b;
        if (que[i].op == 'Q') std::cin >> que[i].c;
        else arr[++xpp] = que[i].b;
    }
    std::copy(arr + 1, arr + xpp + 1, carr + 1);
    std::sort(carr + 1, carr + xpp + 1);
    int f = std::unique(carr + 1, carr + xpp + 1) - carr;
    for (int i = 1; i <= n; i++) 
        arr[i] = std::lower_bound(carr + 1, carr + f, arr[i]) - carr; 
    for (int i = 1; i <= n; i++) st.add(1, 1, f - 1, arr[i], i, 1);
    for (int i = 1; i <= q; i++) {
        int op = que[i].op, a = que[i].a, b = que[i].b, c = que[i].c;
        if (op == 'Q') std::cout << carr[st.query(1, 1, f - 1, a, b, c)] << "\n";
        else st.add(1, 1, f - 1, arr[a], a, -1), arr[a] = std::lower_bound(carr + 1, carr + f, b) - carr, st.add(1, 1, f - 1, arr[a], a, 1);
    }
    return 0;
}