#include<iostream>
#include<algorithm>
#include<random>
const int sz = 5e4 + 10;
const int inf = 0x7fffffff;
std::mt19937 rnd(20230126);
int arr[sz], n, q;
struct treap {
    struct node {
        int val, cnt, lson, rson, size;
        unsigned key;
        node& operator^=(const int &v) {
            val = v, cnt = size = 1, key = rnd();
            return *this;
        }
    } tree[sz << 6];
    int num;
    void resize(int pos) {
        tree[pos].size = tree[pos].cnt + tree[tree[pos].lson].size + tree[tree[pos].rson].size;
    }
    void rotateleft(int &p) {
        int tmp = tree[p].rson;
        tree[p].rson = tree[tmp].lson;
        tree[tmp].lson = p;
        tree[tmp].size = tree[p].size;
        resize(p);
        p = tmp;
    }
    void rotateright(int &p) {
        int tmp = tree[p].lson;
        tree[p].lson = tree[tmp].rson;
        tree[tmp].rson = p;
        tree[tmp].size = tree[p].size;
        resize(p);
        p = tmp;
    }
    void insert(int &pos, int val) {
        if (pos == 0) return pos = ++num, tree[pos] ^= val, void();
        ++tree[pos].size;
        if (val == tree[pos].val) ++tree[pos].cnt;
        else if (val < tree[pos].val) {
            insert(tree[pos].lson, val);
            if (tree[pos].key > tree[tree[pos].lson].key) rotateright(pos);
        } else {
            insert(tree[pos].rson, val);
            if (tree[pos].key > tree[tree[pos].rson].key) rotateleft(pos);
        }
    }
    bool erase(int &pos, int val) {
        if (pos == 0) return false;
        if (val < tree[pos].val) {
            bool successErase = erase(tree[pos].lson, val);
            if (successErase) tree[pos].size--;
            return successErase;
        } else if (val > tree[pos].val) {
            bool successErase = erase(tree[pos].rson, val);
            if (successErase) tree[pos].size--;
            return successErase;
        } else {
            if (tree[pos].cnt > 1) return --tree[pos].cnt, --tree[pos].size, true;
            else if (tree[pos].lson && tree[pos].rson) {
                if (tree[tree[pos].lson].key < tree[tree[pos].rson].key) 
                    return rotateright(pos), erase(pos, val);
                else return rotateleft(pos), erase(pos, val);
            } else {
                pos = tree[pos].lson | tree[pos].rson;
                return true;
            }            
        }
    }
    int rank(int pos, int val) {
        if (pos == 0) return 1;
        if (val == tree[pos].val) return tree[tree[pos].lson].size + 1;
        else if (val < tree[pos].val) return rank(tree[pos].lson, val);
        else return tree[tree[pos].lson].size + tree[pos].cnt + rank(tree[pos].rson, val);
    }
    int prev(int pos, int val) {
        int res = -inf;
        while (pos != 0) {
            if (val > tree[pos].val) 
                res = tree[pos].val, pos = tree[pos].rson;
            else pos = tree[pos].lson;
        }
        return res;
    }
    int post(int pos, int val) {
        int res = inf;
        while (pos != 0) {
            if (val < tree[pos].val) 
                res = tree[pos].val, pos = tree[pos].lson;
            else pos = tree[pos].lson;
        }
        return res;
    }
} treap;
struct ST {
    int tree[sz << 2];
    void build(int p, int ln, int rn) {
        for (int i = ln; i <= rn; i++) treap.insert(tree[p], arr[i]);
        if (ln == rn) return;
        int mid = ln + rn >> 1;
        build(p << 1, ln, mid);
        build(p << 1 | 1, mid + 1, rn);
    }
    void update(int p, int ln, int rn, int pos, int val) {
        treap.erase(tree[p], arr[pos]), treap.insert(tree[p], val);
        if (ln == rn) return;
        int mid = ln + rn >> 1;
        if (pos <= mid) update(p << 1, ln, mid, pos, val);
        else update(p << 1 | 1, mid + 1, rn, pos, val);
    }
    int queryRank(int p, int ln, int rn, int l, int r, int val) {
        if (ln >= l && rn <= r) return treap.rank(tree[p], val);
        int mid = ln + rn >> 1, res = 0;
        if (l <= mid) res += queryRank(p << 1, ln, mid, l, r, val);
        if (r > mid) res += queryRank(p << 1 | 1, mid + 1, rn, l, r, val);
        if (l <= mid && r > mid) res--;
        return res;
    }
    int queryKth(int l, int r, int k) {
        int ql = 1, qr = 1e8;
        while (l != r) {
            int mid = ql + qr >> 1;
            if (queryRank(1, 1, n, ql, qr, mid) - 1 < k) ql = mid + 1;
            else qr = mid;
        }
        return ql - 1;
    }
    int queryPrev(int p, int ln, int rn, int l, int r, int val) {
        if (ln >= l && rn <= r) return treap.prev(tree[p], val);
        int mid = ln + rn >> 1, res = -inf;
        if (l <= mid) res = std::max(res, queryPrev(p << 1, ln, mid, l, r, val));
        if (r > mid) res = std::max(res, queryPrev(p << 1 | 1, mid + 1, rn, l, r, val));
        return res;
    }
    int queryPost(int p, int ln, int rn, int l, int r, int val) {
        if (ln >= l && rn <= r) return treap.post(tree[p], val);
        int mid = ln + rn >> 1, res = inf;
        if (l <= mid) res = std::min(res, queryPost(p << 1, ln, mid, l, r, val));
        if (r > mid) res = std::min(res, queryPost(p << 1 | 1, mid + 1, rn, l, r, val));
        return res;
    }
} st;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> q;
    for (int i = 1; i <= n; i++) std::cin >> arr[i];
    st.build(1, 1, n);
    while (q--) {
        int op, l, r, pos, val;
        std::cin >> op;
        if (op == 1) 
            std::cin >> l >> r >> val, std::cout << st.queryRank(1, 1, n, l, r, val) << "\n";
        if (op == 2) 
            std::cin >> l >> r >> val, std::cout << st.queryKth(l, r, val) << "\n";
        if (op == 3) 
            std::cin >> pos >> val, st.update(1, 1, n, pos, val), arr[pos] = val;
        if (op == 4) 
            std::cin >> l >> r >> val, std::cout << st.queryPrev(1, 1, n, l, r, val) << "\n";
        if (op == 5)
            std::cin >> l >> r >> val, std::cout << st.queryPost(1, 1, n, l, r, val) << "\n";
    }
    return 0;
}