//scy的splay代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct node
{
    int d,f,c,n,son[2];
}tr[4010000];int len;
struct tree
{
    int l,r,lc,rc,root;
}t[210000];int tlen;
int a[51000];
void splay_add(int d,int f)
{
    len++;
    tr[len].d=d;tr[len].f=f;
    tr[len].c=1;tr[len].n=1;
    tr[len].son[0]=tr[len].son[1]=0;
    if(tr[f].d>d)tr[f].son[0]=len;
    else         tr[f].son[1]=len;
}
void splay_update(int x)
{
    int lc=tr[x].son[0],rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}
void splay_rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;
    int r,R;
      
    r=tr[x].son[w];R=f;
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;
      
    r=x;R=ff;
    if(tr[ff].son[0]==f)tr[R].son[0]=r;
    else tr[R].son[1]=r;
    tr[r].f=R;
      
    r=f;R=x;
    tr[R].son[w]=r;
    tr[r].f=R;
      
    splay_update(f);
    splay_update(x);
}
void splay_splay(int wt,int x,int rt)//wt表示这棵伸展树在线段树的那一个节点上 
{
    while(tr[x].f!=rt)
    {
        int f=tr[x].f,ff=tr[f].f;
        if(ff==rt)
        {
            if(x==tr[f].son[0])splay_rotate(x,1);
            else               splay_rotate(x,0);
        }
        else
        {
                 if(tr[f].son[0]==x&&tr[ff].son[0]==f){splay_rotate(f,1);splay_rotate(x,1);}
            else if(tr[f].son[1]==x&&tr[ff].son[0]==f){splay_rotate(x,0);splay_rotate(x,1);}
            else if(tr[f].son[0]==x&&tr[ff].son[1]==f){splay_rotate(x,1);splay_rotate(x,0);}
            else if(tr[f].son[1]==x&&tr[ff].son[1]==f){splay_rotate(f,0);splay_rotate(x,0);}
        }
    }
    if(rt==0)t[wt].root=x;
}
int splay_findip(int wt,int d)
{
    int x=t[wt].root;
    while(tr[x].d!=d)
    {
        if(tr[x].d>d)
        {
            if(tr[x].son[0]==0)break;
            x=tr[x].son[0];
        }
        else if(tr[x].d<d)
        {
            if(tr[x].son[1]==0)break;
            x=tr[x].son[1];
        }
    }
    return x;
}
void splay_ins(int wt,int d)
{
    int x=splay_findip(wt,d);
    if(tr[x].d==d)
    {
        tr[x].n++;
        splay_update(x);
        splay_splay(wt,x,0);
    }
    else
    {
        splay_add(d,x);
        splay_update(x);
        splay_splay(wt,len,0);
    }
}
void seg_bt(int l,int r)
{
    tlen++;int now=tlen;
    t[now].l=l;t[now].r=r;
    splay_add(-2147483647,0);t[now].root=len;
    splay_add(2147483647,len);splay_update(len-1);
    for(int i=l;i<=r;i++)splay_ins(now,a[i]);
    if(l<r)
    {
        int mid=(l+r)/2;
        t[now].lc=tlen+1;seg_bt(l,mid);
        t[now].rc=tlen+1;seg_bt(mid+1,r);
    }
}
int splay_findrank(int wt,int d)
{
    int x=splay_findip(wt,d);splay_splay(wt,x,0);
    int ans=tr[tr[x].son[0]].c;
    if(tr[x].d<d)ans+=tr[x].n;
    return ans;
}
int seq_findrank(int now,int l,int r,int d)
{
    if(t[now].l==l&&t[now].r==r)
    {
        return splay_findrank(now,d)-1;
    }
    int lc=t[now].lc,rc=t[now].rc;
    int mid=(t[now].l+t[now].r)/2;
    if(r<=mid)        return seq_findrank(lc,l,r,d);
    else if(mid+1<=l)return seq_findrank(rc,l,r,d);
    else return seq_findrank(lc,l,mid,d)+seq_findrank(rc,mid+1,r,d);
}
void splay_del(int wt,int d)
{
    int x=splay_findip(wt,d);splay_splay(wt,x,0);
    if(tr[x].d!=d)return ;
    if(tr[x].n>1){tr[x].n--;return ;}
    else if(tr[x].son[0]!=0&&tr[x].son[1]==0){t[wt].root=tr[x].son[0];tr[tr[x].son[0]].f=0;}
    else if(tr[x].son[0]==0&&tr[x].son[1]!=0){t[wt].root=tr[x].son[1];tr[tr[x].son[1]].f=0;}
    else
    {
        int p=tr[x].son[0];
        while(tr[p].son[1]!=0)p=tr[p].son[1];
        splay_splay(wt,p,x);
          
        int r=tr[x].son[1],R=p;
        tr[R].son[1]=r;
        tr[r].f=R;
          
        t[wt].root=R;tr[R].f=0;
        splay_update(R);
    }
}
void seq_del(int now,int pos,int d)
{
    splay_del(now,d);
    if(t[now].l==t[now].r)return ;
    int lc=t[now].lc,rc=t[now].rc;
    int mid=(t[now].l+t[now].r)/2;
    if(pos<=mid)seq_del(lc,pos,d);
    else        seq_del(rc,pos,d);
}
void seq_ins(int now,int pos,int d)
{
    splay_ins(now,d);
    if(t[now].l==t[now].r)return ;
    int lc=t[now].lc,rc=t[now].rc;
    int mid=(t[now].l+t[now].r)/2;
    if(pos<=mid)seq_ins(lc,pos,d);
    else        seq_ins(rc,pos,d);
}
int splay_findqq(int wt,int d)
{
    int x=splay_findip(wt,d);splay_splay(wt,x,0);
    if(tr[x].d>=d&&tr[x].son[0]!=0)
    {
        x=tr[x].son[0];
        while(tr[x].son[1]!=0)x=tr[x].son[1];
    }
    if(tr[x].d>=d)return 0;
    return tr[x].d;
}
int seq_findqq(int now,int l,int r,int k)
{
    if(t[now].l==l&&t[now].r==r)
    {
        return splay_findqq(now,k);
    }
    int lc=t[now].lc,rc=t[now].rc;
    int mid=(t[now].l+t[now].r)/2;
    if(r<=mid)        return seq_findqq(lc,l,r,k);
    else if(mid+1<=l)return seq_findqq(rc,l,r,k);
    else return max(seq_findqq(lc,l,mid,k),seq_findqq(rc,mid+1,r,k));
}
int splay_findhj(int wt,int d)
{
    int x=splay_findip(wt,d);splay_splay(wt,x,0);
    if(tr[x].d<=d&&tr[x].son[1]!=0)
    {
        x=tr[x].son[1];
        while(tr[x].son[0]!=0)x=tr[x].son[0];
    }
    if(tr[x].d<=d)return 999999999;
    return tr[x].d;
}
int seq_findhj(int now,int l,int r,int k)
{
    if(t[now].l==l&&t[now].r==r)
    {
        return splay_findhj(now,k);
    }
    int lc=t[now].lc,rc=t[now].rc;
    int mid=(t[now].l+t[now].r)/2;
    if(r<=mid)        return seq_findhj(lc,l,r,k);
    else if(mid+1<=l)return seq_findhj(rc,l,r,k);
    else return min(seq_findhj(lc,l,mid,k),seq_findhj(rc,mid+1,r,k));
}
int main()
{
    int n,m,mmax=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(mmax<a[i])mmax=a[i];
    }
    tlen=0;len=0;seg_bt(1,n);
      
    int ops,l,r,pos,k;
    while(m--)
    {
        scanf("%d",&ops);
        if(ops==1)
        {
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",seq_findrank(1,l,r,k)+1);
        }
        else if(ops==2)
        {
            scanf("%d%d%d",&l,&r,&k);
            int L=0,R=mmax,ans;
            while(L<=R)
            {
                int mid=(L+R)/2;
                int u=seq_findrank(1,l,r,mid)+1;
                if(k<u)R=mid-1;
                else  {L=mid+1;ans=mid;}
            }
            printf("%d\n",ans);
        }
        else if(ops==3)
        {
            scanf("%d%d",&pos,&k);
            seq_del(1,pos,a[pos]);
            seq_ins(1,pos,k);a[pos]=k;
            if(k>mmax)mmax=k;
        }
        else if(ops==4)
        {
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",seq_findqq(1,l,r,k));
        }
        else if(ops==5)
        {
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",seq_findhj(1,l,r,k));
        }
    }
    return 0;
}