#include <bits/stdc++.h>

using namespace std;

struct FHQTreap
{
    struct node
    {
        int val, sz, l, r, pri;
        node(int val = 0, int sz = 0, int l = 0, int r = 0)
            : val(val), sz(sz), l(l), r(r)
        {
            this->pri = rand();
        }
    };
    vector<node> tree;
    int rt;

    FHQTreap()
    {
        tree.emplace_back(); // add blank value
        rt = 0;
    }
    int addnode(int val)
    {
        tree.emplace_back(val, 1);
        return tree.size() - 1;
    }
    void update(int now) { tree[now].sz = tree[tree[now].l].sz + tree[tree[now].r].sz + 1; }

    void split(int now, int val, int &x, int &y)
    {
        // [,val],[val+1,]
        if (now == 0)
            return x = y = 0, void();
        else if (tree[now].val > val)
        {
            y = now;
            split(tree[now].l, val, x, tree[now].l);
            update(y);
        }
        else
        {
            x = now;
            split(tree[now].r, val, tree[now].r, y);
            update(x);
        }
    }
    int merge(int x, int y)
    {
        if (x == 0 || y == 0)
            return x + y;
        assert(tree[x].val <= tree[y].val);
        if (tree[x].pri <= tree[y].val)
        {
            tree[x].r = merge(tree[x].r, y);
            update(x);
            return x;
        }
        else
        {
            tree[y].l = merge(x, tree[y].l);
            update(y);
            return y;
        }
    }

    void insert(int val)
    {
        int x, y;
        split(rt, val, x, y);
        rt = merge(merge(x, addnode(val)), y);
    }
    void remove(int val)
    {
        int x, y, z;
        split(rt, val, x, z);
        split(x, val - 1, x, y);
        assert(tree[y].val == val);
        y = merge(tree[y].l, tree[y].r);
        rt = merge(merge(x, y), z);
    }

    int get_rank(int val)
    {
        int x, y;
        split(rt, val - 1, x, y);
        int ans = tree[x].sz + 1;
        rt = merge(x, y);
        return ans;
    }
    int get_value(int x, int rk)
    {
        if (rk <= tree[tree[x].l].sz)
        {
            // go left
            return get_value(tree[x].l, rk);
        }
        else if (rk == tree[tree[x].l].sz + 1)
        {
            return tree[x].val;
        }
        else
        {
            return get_value(tree[x].r, rk - tree[tree[x].l].sz - 1);
        }
    }
    int get_pre(int val)
    {
        int x, y;
        split(rt, val - 1, x, y);
        if (x == 0)
            return INT_MIN;
        int ans = get_value(x, tree[x].sz);
        rt = merge(x, y);
        return ans;
    }
    int get_nxt(int val)
    {
        int x, y;
        split(rt, val, x, y);
        if (y == 0)
            return INT_MAX;
        int ans = get_value(y, 1);
        rt = merge(x, y);
        return ans;
    }
};

struct segmant
{
    vector<FHQTreap> seg;
    vector<int> lx, rx, a;
    segmant(int n, vector<int> &init)
        : seg(4 * (n + 1)), lx(4 * (n + 1)), rx(4 * (n + 1))
    {
        assert(n + 1 == init.size());
        seg.emplace_back();
        build(1, n, 1, init);
        a = init;
    }
    void build(int l, int r, int x, vector<int> &init)
    {
        for (int i = l; i <= r; i++)
            seg[x].insert(init[i]);
        if (l == r)
            return;
        int m = (l + r) >> 1;
        lx[x] = l, rx[x] = r;
        build(l, m, x * 2, init);
        build(m + 1, r, x * 2 + 1, init);
    }

    int query_seg_rk(int l, int r, int val, int x)
    {
        if (lx[x] > r || rx[x] < l)
        {
            // no collapsing part
            return 0;
        }
        else if (lx[x] >= l && rx[x] <= r)
        {
            // seg x is in [l,r]
            return seg[x].get_rank(val) - 1;
        }
        else
        {
            return query_seg_rk(l, r, val, x * 2) + query_seg_rk(l, r, val, x * 2 + 1);
        }
    }
    int query_seg_val(int l, int r, int rk, int x)
    {
        // bin split answer!
        int b = 1, e = 1e8 + 5, ans = -1;
        while (b <= e)
        {
            int mid = (b + e) >> 1;
            int tmp = query_seg_rk(l, r, mid, 1);
            if (tmp + 1 <= rk)
            {
                ans = mid;
                b = mid + 1;
            }
            else
            {
                e = mid - 1;
            }
        }
        return ans;
    }

    void modify(int p, int val, int l, int r, int x)
    {
        seg[x].remove(a[p]);
        seg[x].insert(val);
        if (l != r)
        {
            int mid = (l + r) >> 1;
            if (p <= mid)
            {
                // p is on left son
                modify(p, val, l, mid, x * 2);
            }
            else
            {
                modify(p, val, mid + 1, r, x * 2 + 1);
            }
        }
    }

    int query_seg_pre(int l, int r, int val, int x)
    {
        if (lx[x] > r || rx[x] < l)
        {
            // no collapsing part
            return INT_MIN;
        }
        else if (lx[x] >= l && rx[x] <= r)
        {
            // seg x is in [l,r]
            return seg[x].get_pre(val);
        }
        else
        {
            return max(query_seg_pre(l, r, val, x * 2), query_seg_pre(l, r, val, x * 2 + 1));
        }
    }
    int query_seg_nxt(int l, int r, int val, int x)
    {
        if (lx[x] > r || rx[x] < l)
        {
            // no collapsing part
            return INT_MAX;
        }
        else if (lx[x] >= l && rx[x] <= r)
        {
            // seg x is in [l,r]
            return seg[x].get_nxt(val);
        }
        else
        {
            return min(query_seg_nxt(l, r, val, x * 2), query_seg_nxt(l, r, val, x * 2 + 1));
        }
    }
};

int main()
{
    // remember to change val[p]
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<int> init(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> init[i];
    auto tree = segmant(n, init);
    while (m--)
    {
        int op, l, r, k, p, val;
        cin >> op;
        switch (op)
        {
        case 1:
            cin >> l >> r >> val;
            cout << tree.query_seg_rk(l, r, val, 1) + 1 << "\n";
            break;
        case 2:
            cin >> l >> r >> k;
            cout << tree.query_seg_val(l, r, k, 1) << "\n";
            break;
        case 3:
            cin >> p >> val;
            tree.modify(p, val, 1, n, 1);
            tree.a[p] = val;
            break;
        case 4:
            cin >> l >> r >> val;
            cout << tree.query_seg_pre(l, r, val, 1) << "\n";
            break;
        case 5:
            cin >> l >> r >> val;
            cout << tree.query_seg_nxt(l, r, val, 1) << "\n";
            break;
        }
    }
    return 0;
}