#include <bits/stdc++.h>
#define re register
#define il inline
#define ri re int
#define fr(a, b, c) for (ri a = (b); a <= (c); ++a)
#define ur(a, b, c) for (ri a = (b); a >= (c); --a)
#define ef else if
using namespace std;

const int inf = INT_MAX, N = 50005;

int n, m, a[N], op, x, y, z;

namespace BalancedTree {
    struct node { int l, r, val, dat, cnt, siz; } T[N * 100];
    #define l(p) T[p].l
    #define r(p) T[p].r
    #define val(p) T[p].val
    #define dat(p) T[p].dat
    #define cnt(p) T[p].cnt
    #define siz(p) T[p].siz
    int tot;
    il int New(ri val) {
        tot++;
        val(tot) = val, dat(tot) = rand() << 15 | rand();
        cnt(tot) = siz(tot) = 1;
        return tot;
    } struct Treap {
        int rt;
        Treap() { rt = New(-inf), r(rt) = New(inf), pushup(rt); }
        il void pushup(ri p) { siz(p) = siz(l(p)) + siz(r(p)) + cnt(p); }
        il void zig(ri &p) { ri q = l(p); l(p) = r(q), r(q) = p, p = q, pushup(r(p)), pushup(p); }
        il void zag(ri &p) { ri q = r(p); r(p) = l(q), l(q) = p, p = q, pushup(l(p)), pushup(p); }
        void insert(ri &p, ri val) {
            if (!p) { p = New(val); return; }
            if (val == val(p)) { ++cnt(p), ++siz(p); return; }
            if (val < val(p)) { insert(l(p), val); if (dat(l(p)) > dat(p)) zig(p); }
            else              { insert(r(p), val); if (dat(r(p)) > dat(p)) zag(p); }
            pushup(p);
        } void remove(ri &p, ri val) {
            if (!p) return;
            if (val == val(p)) {
                if (cnt(p) > 1) { --cnt(p), --siz(p); return; }
                if (l(p) || r(p)) {
                    if (!r(p) || dat(l(p)) > dat(r(p))) zig(p), remove(r(p), val);
                    else zag(p), remove(l(p), val);
                    pushup(p);
                } else { p = 0; return; }
            } remove(val < val(p) ? l(p) : r(p), val), pushup(p);
        } int getrk(ri p, ri val) {
            if (!p) return 1;
            if (val == val(p)) return siz(l(p)) + 1;
            if (val < val(p)) return getrk(l(p), val);
            else return siz(l(p)) + cnt(p) + getrk(r(p), val);
        } int getpre(ri val) {
            ri ans = -inf, p = rt;
            while (p) {
                if (val == val(p)) {
                    if (l(p)) { for (p = l(p); r(p); p = r(p)); return val(p); }
                    break;
                } if (val(p) < val && val(p) > ans) ans = val(p);
                p = val < val(p) ? l(p) : r(p);
            } return ans;
        } int getnxt(ri val) {
            ri ans = inf, p = rt;
            while (p) {
                if (val == val(p)) {
                    if (r(p)) { for (p = r(p); l(p); p = l(p)); return val(p); }
                    break;
                } if (val(p) > val && val(p) < ans) ans = val(p);
                p = val < val(p) ? l(p) : r(p);
            } return ans;
        }
    };
    #undef l
    #undef r
} namespace SegmentTree {
    struct Seg { int l, r; BalancedTree::Treap tr; } t[N << 2];
    #define lson (p << 1)
    #define rson (p << 1 | 1)
    #define l(p) t[p].l
    #define r(p) t[p].r
    #define tr(p) t[p].tr
    void build(ri p, ri l, ri r) {
        l(p) = l, r(p) = r;
        fr (i, l, r) tr(p).insert(tr(p).rt, a[i]);
        if (l == r) return;
        ri mid = (l + r) >> 1;
        build(lson, l, mid), build(rson, mid + 1, r);
    } void change(ri p, ri x, ri k) {
        tr(p).remove(tr(p).rt, a[x]), tr(p).insert(tr(p).rt, k);
        if (l(p) == r(p)) { a[x] = k; return; }
        ri mid = (l(p) + r(p)) >> 1;
        change(x <= mid ? lson : rson, x, k);
    } int getrk(ri p, ri l, ri r, ri x) {
        if (l <= l(p) && r >= r(p)) return tr(p).getrk(tr(p).rt, x) - 2;
        ri mid = (l(p) + r(p)) >> 1;
        if (r <= mid) return getrk(lson, l, r, x);
        if (l > mid)  return getrk(rson, l, r, x);
        return getrk(lson, l, r, x) + getrk(rson, l, r, x);
    } int getpre(ri p, ri l, ri r, ri x) {
        if (l <= l(p) && r >= r(p)) return tr(p).getpre(x);
        ri mid = (l(p) + r(p)) >> 1;
        if (r <= mid) return getpre(lson, l, r, x);
        if (l > mid)  return getpre(rson, l, r, x);
        return max(getpre(lson, l, r, x), getpre(rson, l, r, x));
    } int getnxt(ri p, ri l, ri r, ri x) {
        if (l <= l(p) && r >= r(p)) return tr(p).getnxt(x);
        ri mid = (l(p) + r(p)) >> 1;
        if (r <= mid) return getnxt(lson, l, r, x);
        if (l > mid)  return getnxt(rson, l, r, x);
        return min(getnxt(lson, l, r, x), getnxt(rson, l, r, x));
    }
} using namespace SegmentTree;

il void read(ri &a, ri ch = 0, ri f = 1) {
    while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
    for (a = 0; isdigit(ch); ch = getchar()) a = (a << 3) + (a << 1) + (ch ^ 48);
    a *= f;
} void write(ri x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10); putchar(x % 10 ^ 48);
} int main() {
    srand(time(0));
    read(n), read(m); fr (i, 1, n) read(a[i]);
    build(1, 1, n);
    while (m--) {
        read(op);
        if (op == 1) read(x), read(y), read(z), write(getrk(1, x, y, z) + 1), putchar(10);
        ef (op == 3) read(x), read(y), change(1, x, y);
        ef (op == 4) read(x), read(y), read(z), write(getpre(1, x, y, z)), putchar(10);
        ef (op == 5) read(x), read(y), read(z), write(getnxt(1, x, y, z)), putchar(10);
        else {
            read(x), read(y), read(z);
            ri l = 0, r = 1e8;
            while (l < r) {
                ri mid = (l + r + 1) >> 1;
                if (getrk(1, x, y, mid) + 1 <= z) l = mid;
                else r = mid - 1;
            } write(l), putchar(10);
        }
    }
    return 0;
}