#6在6000+行错误，#10在13000+行错误

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int cnt = 0, f = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -f;
        c = getchar();
    }
    while (isdigit(c))
    {
        cnt = (cnt << 3) + (cnt << 1) + (c ^ 48);
        c = getchar();
    }
    return cnt * f;
}
const int INF = 2147483647;
const int N = 60 * (int)1e5 + 10;
int a[N], rt[N << 2], ans, n, m, opr, l, r, k;
struct BST
{
    int ch[N][2], val[N], fa[N], cnt[N], siz[N];
    int tot;
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
    void Init()
    {
        memset(ch, 0, sizeof(ch));
        memset(val, 0, sizeof(val));
        memset(fa, 0, sizeof(fa));
        memset(cnt, 0, sizeof(cnt));
        memset(siz, 0, sizeof(siz));
    }
    void update(int p)
    {
        siz[p] = siz[ls(p)] + siz[rs(p)] + cnt[p];
    }
    void rotate(int x)
    {
        int y = fa[x], z = fa[y];
        int k = (x == rs(y));
        ch[z][y == rs(z)] = x;
        fa[x] = z;
        ch[y][k] = ch[x][k ^ 1];
        fa[ch[x][k ^ 1]] = y;
        ch[x][k ^ 1] = y;
        fa[y] = x;
        update(y), update(x);
    }
    void splay(int x, int goal, int &root)
    {
        while (fa[x] != goal)
        {
            int y = fa[x], z = fa[y];
            if (z != goal)
                (ls(z) == y) ^ (ls(y) == x) ? rotate(x) : rotate(y);
            rotate(x);
        }
        if (!goal)
            root = x;
    }
    void insert(int x, int &root)
    {
        if (!root)
        {
            root = ++tot;
            siz[root] = cnt[root] = 1;
            val[root] = x;
            return;
        }
        int p = root, Fa = 0;
        while (p && val[p] != x)
            siz[p]++, Fa = p, p = ch[p][x > val[p]];
        if (p)
            ++cnt[p];
        else
        {
            p = ++tot;
            if (Fa)
                ch[Fa][x > val[Fa]] = p;
            fa[p] = Fa, siz[p] = cnt[p] = 1, val[p] = x;
        }
        splay(p, 0, root);
    }
    int pre(int x, int &root)
    {
        int p = root, res = -2147483647;
        while (p)
        {
            if (val[p] > res && val[p] < x)
                res = val[p];
            p = ch[p][val[p] < x];
        }
        return res;
    }
    int suc(int x, int &root)
    {
        int p = root, res = 2147483647;
        while (p)
        {
            if (val[p] < res && val[p] > x)
                res = val[p];
            p = ch[p][val[p] < x];
        }
        return res;
    }
    int find(int x, int root)
    {
        int p = root;
        while (p && val[p] != x)
            p = ch[p][val[p] < x];
        return p;
    }
    int rk(int x, int &root)
    {
        int p = root, ans = 0;
        while (p)
        {
            if (x < val[p])
                p = ls(p);
            else
            {
                ans += siz[ls(p)];
                if (val[p] == x)
                    return splay(p, 0, root), ans;
                ans += cnt[p];
                p = rs(p);
            }
        }
        return ans;
    }
    void Delete(int x, int &root)
    {
        int pos = find(x, root);
        if (!pos)
            return;
        if (cnt[pos] > 1)
        {
            --siz[pos];
            --cnt[pos];
            return;
        }
        splay(pos, 0, root);
        if (!ls(pos))
        {
            root = rs(pos);
            fa[root] = 0;
            return;
        }
        int lef = ls(pos), rig = rs(pos);
        while (rs(lef))
            lef = rs(lef);
        splay(lef, 0, root);
        fa[rig] = lef, rs(lef) = rig;
        update(lef);
    }
} Splay;
struct segmentTree
{
    int l[N << 2], r[N << 2];
    void build(int p, int L, int R)
    {
        l[p] = L, r[p] = R;
        for (register int i = L; i <= R; ++i)
            Splay.insert(a[i], rt[p]);
        if (L == R)
            return;
        int mid = (L + R) >> 1;
        build(p << 1, L, mid);
        build(p << 1 | 1, mid + 1, R);
    }
    int Rank(int p, int L, int R, int val)
    {
        int ans = 0;
        if (L <= l[p] && R >= r[p])
            return Splay.rk(val, rt[p]);
        int mid = (l[p] + r[p]) >> 1;
        if (L <= mid)
            ans += Rank(p << 1, L, R, val);
        if (R > mid)
            ans += Rank(p << 1 | 1, L, R, val);
        return ans;
    }
    int kth(int L, int R, int val)
    {
        int l = 0, r = (int)1e8;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (Rank(1, L, R, mid) + 1 <= val)
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }
    void modify(int p, int x, int pos, int cur)
    {
        Splay.Delete(x, rt[p]);
        Splay.insert(cur, rt[p]);
        if (l[p] == r[p])
        {
            a[pos] = cur;
            return;
        }
        int mid = (l[p] + r[p]) >> 1;
        if (pos <= mid)
            modify(p << 1, x, pos, cur);
        else
            modify(p << 1 | 1, x, pos, cur);
    }
    int Pre(int p, int L, int R, int x)
    {
        if (L <= l[p] && R >= r[p])
            return Splay.pre(x, rt[p]);
        int ans = -INF;
        int mid = (l[p] + r[p]) >> 1;
        if (L <= mid)
            ans = max(ans, Pre(p << 1, L, R, x));
        if (R > mid)
            ans = max(ans, Pre(p << 1 | 1, L, R, x));
        return ans;
    }
    int Suc(int p, int L, int R, int x)
    {
        if (L <= l[p] && R >= r[p])
            return Splay.suc(x, rt[p]);
        int ans = INF;
        int mid = (l[p] + r[p]) >> 1;
        if (L <= mid)
            ans = min(ans, Suc(p << 1, L, R, x));
        if (R > mid)
            ans = min(ans, Suc(p << 1 | 1, L, R, x));
        return ans;
    }
} segT;
int main()
{
    n = read(), m = read();
    Splay.Init();
    for (register int i = 1; i <= n; ++i)
        a[i] = read();
    segT.build(1, 1, n);
    for (register int i = 1; i <= m; ++i)
    {
        opr = read();
        if (opr == 1)
        {
            l = read(), r = read(), k = read();
            printf("%d\n", segT.Rank(1, l, r, k) + 1);
        }
        if (opr == 2)
        {
            l = read(), r = read(), k = read();
            printf("%d\n", segT.kth(l, r, k));
        }
        if (opr == 3)
        {
            l = read(), k = read();
            segT.modify(1, a[l], l, k), a[l] = k;
        }
        if (opr == 4)
        {
            l = read(), r = read(), k = read();
            printf("%d\n", segT.Pre(1, l, r, k));
        }
        if (opr == 5)
        {
            l = read(), r = read(), k = read();
            printf("%d\n", segT.Suc(1, l, r, k));
        }
    }
    return 0;
}