#1、#3~#8WA

#2、#9TLE

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
const int maxl=3e2+5;
int a[maxn],b[maxn],sd[maxn],l[maxl],r[maxl],s,n,m;
inline int read(){
	int x=0,f=1;
    char ch=getchar();
	while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
	while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;
        ch=getchar();
    }
	return x*f;
}
void write(int k,char ch=0){
	if(k<0){
		k=-k;
		putchar('-');
	}
	if(k>=10)
		write(k/10,0);
	putchar(k%10+'0');
	if(ch) putchar(ch);
}
void init(){
    s=sqrt(n);
    for(int i=1;i<=s;i++){
        l[i]=r[i-1]+1;
        r[i]=i*s;
    }
    r[s]=n;
    for(int i=1;i<=s;i++)
        for(int j=l[i];j<=r[i];j++)
            b[j]=i;
}
pair<int,bool> get_k(int x,int y,int k){
    int ks=b[x],kd=b[y];
    bool flag=false;
    if(ks==kd){
        int j=1;
        for(int i=x;i<=y;i++)
            if(a[i]<k) j++;
            else if(a[i]==k) flag=true;
        return {j,flag};
    }
    int j=1;
    for(int i=x;i<=r[ks];i++)
        if(a[i]<k) j++;
        else if(a[i]==k) flag=true;
    for(int i=l[kd];i<=y;i++)
        if(a[i]<k) j++;
        else if(a[i]==k) flag=true;
    for(int i=ks+1;i<kd;i++){
        int t=(lower_bound(sd+l[i],sd+r[i]+1,k)-sd)-l[i]-1;
        if(t>0) j+=t;
        else if(sd[t+1]==k) flag=true;
    }
    return {j,flag};
}
int get_pre(int x,int y,int k){
    int ks=b[x],kd=b[y];
    if(ks==kd){
        int j=-2147483647;
        for(int i=x;i<=y;i++)
            if(a[i]<k) j=max(j,a[i]);
        return j;
    }
    int j=-2147483647;
    for(int i=x;i<=r[ks];i++)
        if(a[i]<k) j=max(j,a[i]);
    for(int i=l[kd];i<=y;i++)
        if(a[i]<k) j=max(j,a[i]);
    for(int i=ks+1;i<kd;i++){
        int t=lower_bound(sd+l[i],sd+r[i]+1,k)-sd;
        if(t>l[i]) j=max(j,sd[t-1]);
    }
    return j;
}
int get_nxt(int x,int y,int k){
    int ks=b[x],kd=b[y];
    if(ks==kd){
        int j=2147483647;
        for(int i=x;i<=y;i++)
            if(a[i]>k) j=min(j,a[i]);
        return j;
    }
    int j=2147483647;
    for(int i=x;i<=r[ks];i++)
        if(a[i]>k) j=min(j,a[i]);
    for(int i=l[kd];i<=y;i++)
        if(a[i]>k) j=min(j,a[i]);
    for(int i=ks+1;i<kd;i++){
        int t=upper_bound(sd+l[i],sd+r[i]+1,k)-sd;
        if(t<=r[i]) j=min(j,sd[t]);
    }
    return j;
}
int get_kth(int x,int y,int k){
    int l1=0,r1=1e8,ans,mid;
    // for(int i=x;i<=::r[b[x]];i++)
    //     l=min(l,a[i]),r=max(r,a[i]);
    // for(int i=::l[b[y]];i<=y;i++)
    //     l=min(l,a[i]),r=max(r,a[i]);
    // for(int i=b[x]+1;i<b[y];i++)
    //     l=min(sd[::l[i]],l),r=max(sd[::r[i]],r);
    while(l1<=r1){
        mid=(l1+r1)>>1;
        int ch=get_k(x,y,mid).first;
        if(ch>=k){
            r1=mid-1;
            ans=mid;
        }else{
            l1=mid+1;
        }
    }
    // cout<<ans<<endl;
    bool flg=get_k(x,y,ans).second;
    if(!flg){
        int f=get_pre(x,y,ans);
        int g=get_nxt(x,y,ans);
        if(get_k(x,y,g).first>k){
            return f;
        }else{
            return g;
        }
    }
    return ans;
}
void update(int id,int k){
    int kk=b[id];
    for(int i=l[kk];i<=r[kk];i++){
        if(i==id) a[i]=k;
        sd[i]=a[i];
    }
    sort(sd+l[kk],sd+r[kk]+1);
}
int main(){
    n=read();
    m=read();
    init();
    for(int i=1;i<=n;i++)
        sd[i]=a[i]=read();
    for(int i=1;i<=s;i++)
        sort(sd+l[i],sd+r[i]+1);
    while(m--){
        int opt;
        cin>>opt;
        if(opt==1){
            int l,r,k;
            cin>>l>>r>>k;
            write(get_k(l,r,k).first,'\n');
        }else if(opt==2){
            int l,r,k;
            cin>>l>>r>>k;
            write(get_kth(l,r,k),'\n');
        }else if(opt==3){
            int pos,k;
            cin>>pos>>k;
            update(pos,k);
        }else if(opt==4){
            int l,r,k;
            cin>>l>>r>>k;
            write(get_pre(l,r,k),'\n');
        }else{
            int l,r,k;
            cin>>l>>r>>k;
            write(get_nxt(l,r,k),'\n');
        }
    }
    return 0;
}