//这里打的是线段树上加平衡树 //即每一个线段树的节点上都有一棵splay树  #include<cstdio> #include<iostream> #include<cctype> #include<cstring> #include<algorithm> using namespace std;  inline int read(){     int s=0;bool flag=true;char ch=getchar();     while(!isdigit(ch)){if(ch=='-')flag=false;ch=getchar();}     while(isdigit(ch)){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}     return flag?s:-s; }  inline void print_ans(int x){     if(x<0)putchar('-'),x=-x;     if(x>9)print_ans(x/10);     putchar(x%10+'0'); } inline void print(int x){print_ans(x),puts("");}  #define max(a,b) a=max(a,b)  #define min(a,b) a=min(a,b) const int n=4e6+5; const int inf=2147483647; int max,n,m,ans,w[n];  //----------上面是基础数据，输入优化等乱七八糟的东西   int tot,root[n];  struct splay_tree{int son[2],val,size,cnt,father;}t[n]; #define ls(x)     t[x].son[0] #define rs(x)     t[x].son[1] #define val(x)     t[x].val #define sze(x)     t[x].size #define cnt(x)     t[x].cnt #define fa(x)    t[x].father //不为别的，看小括号比看中括号爽  inline void splay_update(int x){     sze(x)=(ls(x)?sze(ls(x)):0)+(rs(x)?sze(rs(x)):0)+cnt(x); }  inline void splay_clear(int x){ls(x)=rs(x)=fa(x)=cnt(x)=sze(x)=val(x)=0;}  inline void splay_rotate(int x){     int y=fa(x),z=fa(y);     int jud_x=(rs(y)==x),jud_y=(rs(z)==y);     int w=t[x].son[jud_x^1];     t[y].son[jud_x]=w;if(w)    fa(w)=y;     if(z)t[z].son[jud_y]=x;fa(x)=z;     t[x].son[jud_x^1]=y;fa(y)=x;     splay_update(y),splay_update(x); }  inline void splay_splay(int id,int x,int goal=0){     while(fa(x)!=goal){         int y=fa(x),z=fa(y);         if(z!=goal)(ls(z)==y)^(ls(y)==x)?splay_rotate(x):splay_rotate(y);         splay_rotate(x);     }     if(!goal)    root[id]=x; }  inline int splay_find(int id,int x){     int u=root[id];     while(x){         if(val(u)==x){splay_splay(id,u);return u;}         u=t[u].son[x>val(u)];     }         return 0; }  inline void splay_insert(int id,int x){     int u=root[id];     if(!root[id]){         root[id]=u=++tot;         ls(u)=rs(u)=0,val(u)=x,sze(u)=cnt(u)=1,fa(u)=0;         return ;     }     int pre=0;     while(true){         if(val(u)==x){cnt(u)++;splay_update(pre);break;}         pre=u,u=t[u].son[x>val(u)];         if(!u){             u=++tot;             t[pre].son[x>val(pre)]=u;             ls(u)=rs(u)=0,val(u)=x,sze(u)=cnt(u)=1,fa(u)=pre;             splay_update(pre);break;         }     }     splay_splay(id,u); }  inline int splay_rank(int id,int k){     //以线段树上的id节点为根的splay树上寻找权值k的排名      int x=root[id],sum=0;     while(x){         if(val(x)==k)    return sum+(ls(x) ? sze(ls(x)) : 0);         else if(val(x)<k){             sum+=(ls(x) ? sze(ls(x)) : 0)+cnt(x);             x=rs(x);         }         else    x=ls(x);     }     return sum; }  inline int splay_getpre(int id,int x){     int u=root[id];     while(u){         if(val(u)<x){max(ans,val(u));u=rs(u);}         else u=ls(u);     }     return ans; }  inline int splay_getsuf(int id,int x){     int u=root[id];     while(u){         if(val(u)>x){min(ans,val(u));u=ls(u);}         else u=rs(u);     }     return ans; }  inline int splay_pre(int id){int x=ls(root[id]);while(rs(x))x=rs(x);return x;}//根节点的前驱，用于delete操作  inline void splay_delete(int id,int x){     int u=splay_find(id,x);     if(cnt(u)>1){cnt(u)--;splay_update(u);return ;}     if(!ls(u) && !rs(u)){splay_clear(root[id]);root[id]=0;return ;}     if(!ls(u)){root[id]=rs(u),fa(rs(u))=0;return ;}     if(!rs(u)){root[id]=ls(u),fa(ls(u))=0;return ;}     int pre=splay_pre(id),father=root[id];     splay_splay(id,pre,0);     rs(root[id])=rs(father);     fa(rs(father))=root[id];     splay_clear(father),splay_update(root[id]); }   //----------上面是关于splay的函数，下面是关于segment tree的函数   #define lc     (id<<1) #define rc     (id<<1|1) #define mid    ((l+r)>>1)  inline void seg_insert(int id,int l,int r,int pos,int k){     splay_insert(id,k);     if(l==r)    return ;     if(pos<=mid)    seg_insert(lc,l,mid,pos,k);     else    seg_insert(rc,mid+1,r,pos,k); }  inline void seg_rank(int id,int l,int r,int l,int r,int k){     //在整棵线段树上找到该splay的区间     if(l==l&&r==r){ans+=splay_rank(id,k);return ;}     if(r<=mid)    seg_rank(lc,l,mid,l,r,k);     else if(l>mid) seg_rank(rc,mid+1,r,l,r,k);     else seg_rank(lc,l,mid,l,mid,k),seg_rank(rc,mid+1,r,mid+1,r,k); }  inline void seg_modify(int id,int l,int r,int pos,int k){     //单点修改权值，splay同时更新     splay_delete(id,w[pos]);splay_insert(id,k);     if(l==r){w[pos]=k;return ;}     if(pos<=mid)    seg_modify(lc,l,mid,pos,k);     else    seg_modify(rc,mid+1,r,pos,k);  }  inline void seg_pre(int id,int l,int r,int l,int r,int k){     //查询权值为k的前驱     if(l==l&&r==r){max(ans,splay_getpre(id,k));return ;}     if(r<=mid) seg_pre(lc,l,mid,l,r,k);     else if(l>mid)    seg_pre(rc,mid+1,r,l,r,k);     else seg_pre(lc,l,mid,l,mid,k),seg_pre(rc,mid+1,r,mid+1,r,k); }  inline void seg_suf(int id,int l,int r,int l,int r,int k){     //查询权值为k的后驱     if(l==l&&r==r){min(ans,splay_getsuf(id,k));return ;}     if(r<=mid) seg_suf(lc,l,mid,l,r,k);     else if(l>mid)    seg_suf(rc,mid+1,r,l,r,k);     else seg_suf(lc,l,mid,l,mid,k),seg_suf(rc,mid+1,r,mid+1,r,k); }  //----------其他情况的函数  inline int search_value(int l,int r,int kth){     //寻求l，r区间第k大的数，即区间第k大     int l=0,r=max+1,m;     while(l<r){         m=(l+r)>>1;ans=0;         seg_rank(1,1,n,l,r,m);         if(ans<kth)    l=m+1;         else r=m;     }     return l-1; }  signed main(){     n=read(),m=read();max=-inf;     for(int i=1;i<=n;i++){         w[i]=read();         seg_insert(1,1,n,i,w[i]);         max(max,w[i]);     }     while(m--){         int opt=read();         switch(opt){             case 1:{//区间查k值的排名                  int l=read(),r=read(),k=read();ans=0;                 seg_rank(1,1,n,l,r,k);                 print(ans+1);                 break;             }             case 2:{//区间查第k大                  int l=read(),r=read(),kth=read();                 print(search_value(l,r,kth));                 break;             }             case 3:{//单点修改                  int pos=read(),k=read();                 seg_modify(1,1,n,pos,k);                 break;             }             case 4:{//k的前驱                  int l=read(),r=read(),k=read();ans=-inf;                 seg_pre(1,1,n,l,r,k);                 print(ans);                 break;             }             case 5:{//k的后驱                  int l=read(),r=read(),k=read();ans=inf;                 seg_suf(1,1,n,l,r,k);                 print(ans);                 break;             }         }     }     return 0; }