#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cctype>

#define max(x, y) (x > y ? x : y)

#define min(x, y) (x < y ? x : y)

inline void read(int & x)

{

    x = ;

    int k = ;

    char c = getchar();

    while (!isdigit(c))

        if (c == '-') c = getchar(), k = -;

        else c = getchar();

    while (isdigit(c))

        x = (x << ) + (x << ) + (c ^ ),

        c = getchar();

    x *= k;

}

const int inf = ;

const int N = ;

int n, m, tot, l, r, x, y, z, opt, mxa = -;

int cnt[N], faz[N], val[N], siz[N], a[N], son[N][], root[N];

//=======================================================================

//Splay

inline int Getson(int u) { return son[faz[u]][] == u; }

inline void Pushup(int u) { siz[u] = siz[son[u][]] + siz[son[u][]] + cnt[u]; }

inline int Getmin(int u) { while (son[u][]) u = son[u][]; return u; }

inline int Getmax(int u) { while (son[u][]) u = son[u][]; return u; }

inline int Getx(int rtid, int x)

{

    int u = root[rtid], las = ;

    while (u && val[las = u] != x)

        if (x >= val[u]) u = son[u][];

        else u = son[u][];

    return u ? u : las;

}

void Rotate(int u)

{

    int y = faz[u], z = faz[y], ch = Getson(u);

    int b = son[u][ch ^ ], d = Getson(y);

    son[u][ch ^ ] = y, son[y][ch] = b;

    faz[y] = u, faz[b] = y, faz[u] = z;

    if (z) son[z][d] = u;

    Pushup(y), Pushup(u);

}

void Splay(int rtid, int u, int tar)

{

    while (faz[u] != tar)

    {

        if (faz[faz[u]] != tar)

            if (Getson(u) == Getson(faz[u])) Rotate(faz[u]);

            else Rotate(u);

        Rotate(u);

    }

    if (!tar) root[rtid] = u;

}

inline void Insert(int rtid, int x)

{

    int u = root[rtid], las = ;

    if (!root[rtid])

    {

        root[rtid] = u = ++tot;

        val[u] = x; siz[u] = cnt[u] = ;

        faz[u] = son[u][] = son[u][] = ;

        return;

    }

    while (true)

    {

        ++siz[u];

        if (x == val[u])

        {

            ++cnt[u];

            break;

        }

        las = u;

        if (x > val[u]) u = son[u][];

        else u = son[u][];

        if (!u)

        {

            u = ++tot, val[u] = x, faz[u] = las,

            son[las][x > val[las]] = u;

            son[u][] = son[u][] = ,

            siz[u] = cnt[u] = ;

            break;

        }

    }

    Splay(rtid, u, );

}

inline void Delete(int rtid, int x)

{

    int u = root[rtid];

    while (u)

    if (x == val[u])

    {

        Splay(rtid, u, );

        if (cnt[u] > ) { --cnt[u], --siz[u]; return; }

        if (!son[u][] || !son[u][])

        {

            root[rtid] = son[u][] | son[u][];

            faz[root[rtid]] = ;

            return;

        }

        int newrt = Getmin(son[u][]);

        faz[son[u][]] = ,

        faz[son[u][]] = newrt,

        son[newrt][] = son[u][];

        Splay(rtid, newrt, );

        return;

    }

    else if (x > val[u]) u = son[u][];

    else u = son[u][];

}

inline int Getkth(int rtid, int k)

{

    int u = root[rtid];

    if (siz[u] < k) return -inf;

    while (u)

        if (siz[son[u][]] >= k) u = son[u][];

        else if (siz[son[u][]] + cnt[u] < k) k -= siz[son[u][]] + cnt[u], u = son[u][];

        else return val[u];

}

inline int Getrank(int rtid, int x)

{

//-------------------·½·¨Ò»------------------------

//Wrong Answer

/*    int u = Getx(rtid, x);

    Splay(rtid, u, 0);

    return siz[son[u][0]];

*/

//-------------------·½·¨¶þ------------------------

int sum = , u = root[rtid];

    while (u)

        if (x == val[u]) return sum + siz[son[u][]];

        else if (x > val[u]) sum += siz[son[u][]] + cnt[u], u = son[u][];

        else u = son[u][];

    return sum;

}

int Pre(int rtid, int x)

{

    int u = Getx(rtid, x);

       if (val[u] < x) return val[u];

    Splay(rtid, u, );

    return son[u][] ==  ? -inf : val[Getmax(son[u][])];

}

int Suf(int rtid, int x)

{

    int u = Getx(rtid, x);

       if (val[u] > x) return val[u];

    Splay(rtid, u, );

    return son[u][] ==  ? inf : val[Getmin(son[u][])];

}

//Splay End

//=======================================================================

//Segment tree Begin

#define Root 1, 1, n

#define Lson u << 1, l, mid

#define Rson u << 1 | 1, mid + 1, r

#define ls (u << 1)

#define rs (u << 1 | 1)

#define mid (l + r >> 1)

#define MID (L + R >> 1)

inline void Segins(int u, int l, int r, int p, int x)

{

    Insert(u, x);

    if (l == r) return;

    if (p <= mid) Segins(Lson, p, x);

    else Segins(Rson, p, x);

}

inline void Segmdf(int u, int l, int r, int p, int x)

{

    Delete(u, a[p]), Insert(u, x);

    if (l == r) { a[p] = x; return; }

    if (p <= mid) Segmdf(Lson, p, x);

    else Segmdf(Rson, p, x);

}

inline int Segrak(int u, int l, int r, int x, int y, int z)

{

    if (l == x && r == y) return Getrank(u, z);

    if (y <= mid) return Segrak(Lson, x, y, z);

    if (x > mid) return Segrak(Rson, x, y, z);

    return Segrak(Lson, x, mid, z) + Segrak(Rson, mid + , y, z);

}

inline int Segpre(int u, int l, int r, int x, int y, int z)

{

    if (l == x && r == y) return Pre(u, z);

    if (y <= mid) return Segpre(Lson, x, y, z);

    if (x > mid) return Segpre(Rson, x, y, z);

    return max(Segpre(Lson, x, mid, z), Segpre(Rson, mid + , y, z));

}

inline int Segsuf(int u, int l, int r, int x, int y, int z)

{

    if (l == x && r == y) return Suf(u, z);

    if (y <= mid) return Segsuf(Lson, x, y, z);

    if (x > mid) return Segsuf(Rson, x, y, z);

    return min(Segsuf(Lson, x, mid, z), Segsuf(Rson, mid + , y, z));

}

inline int Segkth(int l, int r, int k)

{

    int cur, L = , R = mxa + ;

    while (L < R)

    {

        cur = Segrak(Root, l, r, MID);

        if (cur < k) L = MID + ;

        else R = MID;

    }

    return L - ;

}

signed main()

{

    read(n), read(m);

    for (int i = ; i <= n; ++i)

    {

        read(a[i]);

        Segins(Root, i, a[i]);

        mxa = max(mxa, a[i]);

    }

    for (int i = ; i <= m; ++i)

    {

        read(opt);

        if (opt == ) read(x), read(y), Segmdf(Root, x, y);

        else

        {

            read(l), read(r), read(x);

            if (opt == ) printf("%d\n", Segrak(Root, l, r, x) + );

            if (opt == ) printf("%d\n", Segkth(l, r, x));

            if (opt == ) printf("%d\n", Segpre(Root, l, r, x));

            if (opt == ) printf("%d\n", Segsuf(Root, l, r, x));

        }

    }

    return ;

}