#include<bits/stdc++.h>
#define INF 2147483647
#define MAXN 500010
using namespace std;
int n,m;
int a[MAXN];
int cnt;
struct node{
    int ls,rs,siz,rk,val;
}t[MAXN*50];
struct FHQtreap{
    int root;
    int mkn(int v)
    {
        t[++cnt].siz=1;
        t[cnt].val=v;
        t[cnt].rk=rand();
        return cnt;
    }
    void update(int rt)
    {
        if(!rt) return;
        t[rt].siz=t[t[rt].ls].siz+t[t[rt].rs].siz+1;
    }
    void split(int rt,int &l,int &r,int k)
    {
        if(rt==0)
        {
            l=r=0;
            return;
        }
        if(t[rt].val<=k)
        {
            l=++cnt;
            t[l]=t[rt];
            split(t[l].rs,t[l].rs,r,k);
            update(l);
        }
        else
        {
            r=++cnt;
            t[r]=t[rt];
            split(t[r].ls,l,t[r].ls,k);
            update(r);
        }
    }
    int merge(int l,int r)
    {
        if(!l||!r) return l|r;
        int k=++cnt;
        if(t[l].rk<=t[r].rk)
        {
            t[k]=t[l];
            t[k].rs=merge(t[k].rs,r);
        }
        else
        {
            t[k]=t[r];
            t[k].ls=merge(l,t[k].ls);
        }
        update(k);
        return k;
    }
    void insert(int x)
    {
        int l,r,k;
        split(root,l,r,x);
        root=merge(merge(l,mkn(x)),r);
        //update(root);
    }
    void erase(int x)
    {
        int l,r,k;
        split(root,l,k,x);
        split(l,l,r,x-1);
        r=merge(t[r].ls,t[r].rs);
        root=merge(merge(l,k),r);
        //update(root);
    }
    int get_rank(int x)
    {
        int l,r,res;
        split(root,l,r,x-1);
        res=t[l].siz+1;
        root=merge(l,r);
        return res;
    }
    int kth(int rt,int k)
    {
        if(t[t[rt].ls].siz>=k)
            return kth(t[rt].ls,k);
        if(t[t[rt].ls].siz+1==k)
            return t[rt].val;
        return kth(t[rt].rs,k-t[t[rt].ls].siz-1);
    }
    int get_pre(int x)
    {
        int l,r,k,s;
        split(root,l,r,x-1);
        if(!l) return -INF;
        k=t[l].siz;
        s=kth(l,k);
        root=merge(l,r);
        return s;
    }
    int get_suf(int x)
    {
        int l,r,s;
        split(root,l,r,x);
        if(!r) return INF;
        s=kth(r,1);
        root=merge(l,r);
        return s;
    }
    void build(int l,int r)
    {
    	for(int i=l;i<=r;i++) insert(a[i]);
	}
}treap[MAXN<<2];
struct Segtree{
    void build(int rt,int l,int r)
    {
        treap[rt].build(l,r);
        if(l==r) return;
        int mid=(l+r)>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
    }
    int get_rank(int rt,int l,int r,int ql,int qr,int v)
    {
    	if(r<ql||l>qr) return 0;
        if(ql<=l&&r<=qr)
            return treap[rt].get_rank(v)-1;
        int mid=(l+r)>>1;
        return get_rank(rt<<1,l,mid,ql,qr,v)+get_rank(rt<<1|1,mid+1,r,ql,qr,v);
    }
    void update(int rt,int l,int r,int x,int v)
    {
        treap[rt].erase(a[x]);
        treap[rt].insert(v);
        if(l==r) return;
        int mid=(l+r)>>1;
        if(x<=mid) update(rt<<1,l,mid,x,v);
        else update(rt<<1|1,mid+1,r,x,v);
    }
    int get_pre(int rt,int l,int r,int ql,int qr,int v)
    {
    	if(r<ql||l>qr) return -INF;
        if(ql<=l&&r<=qr)
            return treap[rt].get_pre(v);
        int mid=(l+r)>>1;
        return max(get_pre(rt<<1,l,mid,ql,qr,v),get_pre(rt<<1|1,mid+1,r,ql,qr,v));
    }
    int get_suf(int rt,int l,int r,int ql,int qr,int v)
    {
    	if(r<ql||l>qr) return INF;
        if(ql<=l&&r<=qr)
            return treap[rt].get_suf(v);
        int mid=(l+r)>>1;
        return min(get_suf(rt<<1,l,mid,ql,qr,v),get_suf(rt<<1|1,mid+1,r,ql,qr,v));
    }
    int kth(int ql,int qr,int k)
    {
        int l=0,r=1e8;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(get_rank(1,1,n,ql,qr,mid)+1<=k) l=mid+1;
            else r=mid-1;
        }
        return l-1;
    }
}segtree;
int main()
{
    freopen("P3380_1.in","r",stdin);
    //freopen("my.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    segtree.build(1,1,n);
    //while(m--)
    for(int i=1;i<=m;i++)
    {
        cout<<i<<endl;
        int opt,l,r,k,pos;
        scanf("%d",&opt);
        if(opt==3)
        {
            scanf("%d%d",&pos,&k);
            segtree.update(1,1,n,pos,k);
            a[pos]=k;
        }
        else
        {
            scanf("%d%d%d",&l,&r,&k);
            if(opt==1)
            {
                printf("%d\n",segtree.get_rank(1,1,n,l,r,k)+1);
            }
            else if(opt==2)
            {
                printf("%d\n",segtree.kth(l,r,k));
            }
            else if(opt==4)
            {
                printf("%d\n",segtree.get_pre(1,1,n,l,r,k));
            }
            else if(opt==5)
            {
                printf("%d\n",segtree.get_suf(1,1,n,l,r,k));
            }
        }
    }
    return 0;
}