#include<cstdio>
#include<cstdlib>
#include<ctime>
const int maxn=500001;
namespace treap{
int val[maxn],lc[maxn],rc[maxn],s[maxn],cnt;short key[maxn];
inline int newnode(int x){val[++cnt]=x,lc[cnt]=rc[cnt]=0,s[cnt]=1,key[cnt]=std::rand();return cnt;}
inline void pushup(int x){s[x]=s[lc[x]]+s[rc[x]]+1;}
void split(int rt,int&a,int&b,int x) {
    if(!rt){a=b=0;return;}
    if(val[rt]<=x){a=rt;split(rc[a],rc[a],b,x);}else{b=rt;split(lc[b],a,lc[b],x);}pushup(rt);
}
void merge(int&rt,int a,int b) {
    if(!a||!b){rt=a|b;return;}
    if(key[a]>key[b]){rt=a;merge(rc[rt],rc[rt],b);}else{rt=b;merge(lc[rt],a,lc[rt]);}pushup(rt);
}
inline void ins(int&rt,int x){int a,b;split(rt,a,b,x);merge(a,a,newnode(x));merge(rt,a,b);}
inline void del(int&rt,int x){int a,b;split(rt,a,b,x);split(a,a,rt,x-1);merge(rt,a,b);}
inline int query(int&rt,int l,int r){int a,b,ans;split(rt,a,b,r);split(a,a,rt,l-1);ans=s[rt];merge(a,a,rt);merge(rt,a,b);return ans;}
}
const int maxs=13500028;
int tree[maxs],ch[maxs][2],cnt=1,rt,L,R;
inline int newnode(){tree[cnt]=ch[cnt][0]=ch[cnt][1]=0;return cnt;}
inline void init(){rt=1,L=0,R=1e+8;}inline void move(int d){rt=ch[rt][0]?ch[rt][0]:ch[rt][0]=newnode();if(d)L=(L+R>>1)+1;else R=L+R>>1;}
inline void ins(int x,int y){for(init();treap::ins(tree[rt],y),L!=R;move((L+R>>1)<x));}
inline void del(int x,int y){for(init();treap::del(tree[rt],y),L!=R;move((L+R>>1)<x));}
inline int rank(int l,int r,int x){int ans=0;for(init();L!=R;move((L+R>>1)<x))if((L+R>>1)<x)ans+=treap::query(tree[rt],l,r);return ans;}
inline int kth(int l,int r,int k){int tmp=0,x;for(init();L!=R;move(tmp+x>k),tmp+=tmp+x>k?0:x)x=treap::query(tree[rt],l,r);return L;}
inline int pre(int l,int r,int x){int k=rank(l,r,x)-1;return k?kth(l,r,k):-2147483658;}
inline int nxt(int l,int r,int x){int k=rank(l,r,x+1);return k<=treap::query(tree[1],l,r)?kth(l,r,k):2147483647;}
int a[maxn],n,m,x,op,l,r;
int main() {
    std::scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)std::scanf("%d",&a[i]),ins(i,a[i]);
    for(;m;--m){
        std::scanf("%d",&op);
        switch(op){
            case 1:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",kth(l,r,x));break;
            case 2:std::scanf("%d%d",&l,&x);del(a[l],l);ins(x,l);a[l]=x;break;
            case 3:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",rank(l,r,x));break;
            case 4:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",pre(l,r,x));break;
            default:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",nxt(l,r,x));break;
        }
    }
    return 0;
}