#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
     
const int maxn=50000+5,oo=~0u>>1;
int n,q;
int a[maxn];
struct Treap{
    struct node{
        node* ch[2];
        int v,r,s,c;
        node(int v,node* t):v(v){ ch[0]=ch[1]=t; r=rand(); s=c=1; }
        void push_up() { s=ch[0]->s+ch[1]->s+c; }
    }*root,*null;
    Treap(){
        null=new node(0,NULL);
        null->c=null->s=0; null->r=oo;
        root=null;
    }
    void rotate(node* &o,bool d){
        node* k=o->ch[!d]; o->ch[!d]=k->ch[d]; k->ch[d]=o;
        o->push_up(); k->push_up(); 
        if(o==root) root=k;
        o=k;
    }
    void insert(node* &o,int x){
        if(o==null) o=new node(x,null);
        else{
            if(x==o->v)  o->s++, o->c++;
            else{
                bool d=x>o->v;
                insert(o->ch[d],x);
                if(o->ch[d]<o) rotate(o,!d);
                o->push_up();
            }
        }
    }
    void remove(node* &o,int x) {
        if(x==o->v) {
            if(o->c>1) o->c--,o->s--;           
            else{
                bool d=o->ch[1]->r<o->ch[0]->r;
                if(o->ch[d]==null){
                    delete o;
                    o=null;
                }
                else{
                    rotate(o,!d);
                    remove(o->ch[!d],x);
                    o->push_up();
                }
            }
        }
        else{
            bool d=x>o->v;
            remove(o->ch[d],x);
            o->push_up();
        }
    }
    int rank(int x){
        int ret=0,s;
        for(node *t=root;t!=null;){
            s=t->ch[0]->s+t->c;
            if(x>t->v) ret+=s,t=t->ch[1];
            else t=t->ch[0];
        }
        return ret;
    }
    int pre(int x){
        int ret=-oo;
        for(node* t=root;t!=null;){
            if(t->v<x) ret=t->v,t=t->ch[1];
            else t=t->ch[0];
        }
        return ret;
    }
    int suc(int x){
        int ret=oo;
        for(node* t=root;t!=null;){
            if(t->v>x) ret=t->v,t=t->ch[0];
            else t=t->ch[1];
            }
        return ret;
    }
};
     
struct Segment_Tree{
    Treap tree[maxn<<2];
    void build_tree(int l,int r,int k){
        for(int i=l;i<=r;i++) tree[k].insert(tree[k].root,a[i]);
        if(l==r) return;
        int mid=l+((r-l)>>1);
        build_tree(l,mid,k<<1); build_tree(mid+1,r,k<<1|1);
    }
    int get_rank(int l,int r,int k,int x,int y,int X){
        if(l==x&&r==y) return tree[k].rank(X);
        int mid=l+((r-l)>>1);
        if(y<=mid) return get_rank(l,mid,k<<1,x,y,X);
        else if(x>mid) return get_rank(mid+1,r,k<<1|1,x,y,X);
        else return get_rank(l,mid,k<<1,x,mid,X)+get_rank(mid+1,r,k<<1|1,mid+1,y,X);
    }
    void change(int l,int r,int k,int id,int x){
        tree[k].remove(tree[k].root,a[id]);
        tree[k].insert(tree[k].root,x);
        if(l==r) return;
        int mid=l+((r-l)>>1);
        if(id<=mid) change(l,mid,k<<1,id,x);
        else change(mid+1,r,k<<1|1,id,x);
    }
    int get_pre(int l,int r,int k,int x,int y,int X){
        if(l==x&&r==y) return tree[k].pre(X);
        int mid=l+((r-l)>>1);
        if(y<=mid) return get_pre(l,mid,k<<1,x,y,X);
        else if(x>mid) return get_pre(mid+1,r,k<<1|1,x,y,X);
        else return max(get_pre(l,mid,k<<1,x,mid,X),get_pre(mid+1,r,k<<1|1,mid+1,y,X));
    }
    int get_suc(int l,int r,int k,int x,int y,int X){
        if(l==x&&r==y) return tree[k].suc(X);
        int mid=l+((r-l)>>1);
        if(y<=mid) return get_suc(l,mid,k<<1,x,y,X);
        else if(x>mid) return get_suc(mid+1,r,k<<1|1,x,y,X);
        else return min(get_suc(l,mid,k<<1,x,mid,X),get_suc(mid+1,r,k<<1|1,mid+1,y,X));
    }
    int get_kth(int x,int y,int k){
        int l=0,r=oo;
        while(l<r){
            int mid=l+((r-l)>>1);
            int tmp=get_rank(1,n,1,x,y,mid)+1;
            if(tmp<=k) l=mid+1;
            else r=mid;
        }
        return get_pre(1,n,1,x,y,l);
    }
}T;
     
int main()
{
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    T.build_tree(1,n,1);
    int qry,l,r,k,x,pos;
    for(int i=1;i<=q;i++){
        scanf("%d",&qry);
        switch(qry){
            case 1:
                scanf("%d%d%d",&l,&r,&x);
                printf("%d\n",T.get_rank(1,n,1,l,r,x)+1);break;
            case 2:
                scanf("%d%d%d",&l,&r,&k);
                printf("%d\n",T.get_kth(l,r,k));break;
            case 3:
                scanf("%d%d",&pos,&x);
                T.change(1,n,1,pos,x);
                a[pos]=x;break;
            case 4:
                scanf("%d%d%d",&l,&r,&x);
                printf("%d\n",T.get_pre(1,n,1,l,r,x));break;
            case 5:
                scanf("%d%d%d",&l,&r,&x);
                printf("%d\n",T.get_suc(1,n,1,l,r,x));break;
        }
    }
    return 0;
}