#include <bits/stdc++.h>

#define i64 long long int

#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second

#define eb emplace_back

using namespace std;

inline int Read() 
{
    int res;
    return scanf("%d", &res), res;
}
inline i64 Read64() 
{
    i64 res;
    return scanf("%lld", &res), res;
}

const int INF_32 = 1e9;
const i64 INF_64 = 1e18;

const int N = 50000 + 5, M = 5000000 + 5;

int n, q, a[N];

mt19937 Rng((unsigned)time(NULL));

int ls[M], rs[M], val[M], key[M], sz[M], tot = 0;

struct FHQ 
{
    int rt = 0;
    void Update(int u) 
    {
        sz[u] = sz[ls[u]] + sz[rs[u]] + 1;
    }

    void Split(int u, int x, int &L, int &R) 
    {
        if (!u)
            return L = R = 0, void();

        if (val[u] <= x)
            L = u, Split(rs[u], x, rs[L], R);
        else
            R = u, Split(ls[u], x, L, ls[R]);

        Update(u);
    }

    int Merge(int L, int R) 
    {
        if (!L || !R)
            return L + R;

        if (key[L] > key[R]) 
        {
            rs[L] = Merge(rs[L], R);
            return Update(L), L;
        } 
        else 
        {
            ls[R] = Merge(L, ls[R]);
            return Update(R), R;
        }
    }

    int NewNode(int x) 
    {
        key[++ tot] = Rng(), val[tot] = x, sz[tot] = 1;
        ls[tot] = rs[tot] = 0;
        return tot;
    }

    void Insert(int x) 
    {
        int L, R;
        Split(rt, x, L, R);
        rt = Merge(Merge(L, NewNode(x)), R);
    }

    void Erase(int x) 
    {
        int L, R, t1, t2;
        Split(rt, x, L, R);
        Split(L, x - 1, t1, t2);
        t2 = Merge(ls[t2], rs[t2]);
        rt = Merge(Merge(t1, t2), R);
    }

    int Rank(int u, int k) 
    {
        if (!u)
            return 0;

        return val[u] < k ? sz[ls[u]] + 1 + Rank(rs[u], k) : Rank(ls[u], k);
    }

    int Kth(int u, int k) 
    {
        if (k == sz[ls[u]] + 1)
            return val[u];

        return k <= sz[ls[u]] ? Kth(ls[u], k) : Kth(rs[u], k - 1 - sz[ls[u]]);
    }
} tr[N << 2];

void Build(int id, int l, int r) 
{
    for (int i = l; i <= r; ++ i)
        tr[id].Insert(a[i]);

    if (l < r) 
    {
        int mid = (l + r) >> 1;
        Build(id << 1, l, mid), Build(id << 1 | 1, mid + 1, r);
    }
}

void Change(int id, int l, int r, int x, int y) 
{
    tr[id].Erase(a[x]), tr[id].Insert(y);

    if (l == r)
        return ;

    int mid = (l + r) >> 1;

    if (x <= mid)
        Change(id << 1, l, mid, x, y);
    else
        Change(id << 1 | 1, mid + 1, r, x, y);
}

int GetRank(int id, int l, int r, int L, int R, int x) 
{
    if (L <= l && r <= R)
        return tr[id].Rank(tr[id].rt, x);

    int mid = (l + r) >> 1, ans = 0;

    if (L <= mid)
        ans += GetRank(id << 1, l, mid, L, R, x);

    if (R > mid)
        ans += GetRank(id << 1 | 1, mid + 1, r, L, R, x);

    return ans;
}

int Kth(int L, int R, int x) 
{
    if (x < 0)
        return -2147483647;

    if (x > R - L + 1)
        return 2147483647;

    int l = 0, r = 100000000, mid, res = 2147483647;

    while (l <= r) 
    {
        mid = (l + r) >> 1;

        if (GetRank(1, 1, n, L, R, mid) <= x)
            res = mid, l = mid + 1;
        else
            r = mid - 1;
    }

    return res;
}

int main() 
{
    n = Read(), q = Read();

    for (int i = 1; i <= n; ++ i)
        a[i] = Read();

    Build(1, 1, n);

    while (q --) 
    {
        int opt = Read();

        if (opt == 1) 
        {
            int l = Read(), r = Read(), k = Read();
            printf("%d\n", GetRank(1, 1, n, l, r, k) + 1);
        }

        if (opt == 2) 
        {
            int l = Read(), r = Read(), k = Read() - 1;
            printf("%d\n", Kth(l, r, k));
        }

        if (opt == 3) 
        {
            int pos = Read(), k = Read();
            Change(1, 1, n, pos, k), a[pos] = k;
        }

        if (opt == 4) 
        {
            int l = Read(), r = Read(), k = Read();
            printf("%d\n", Kth(l, r, GetRank(1, 1, n, l, r, k) - 1));
        }

        if (opt == 5) 
        {
            int l = Read(), r = Read(), k = Read();
            printf("%d\n", Kth(l, r, GetRank(1, 1, n, l, r, k + 1)));
        }
    }

    return 0;
}