#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int res=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+(ch^'0');
		ch=getchar();
	}
	return res;
}
const int maxn=5e4+5;
int n,m,len,num,l[maxn],r[maxn],del[maxn],a[maxn],b[maxn];
inline int f(int x,int k){
	int L=0,R=r[x]-l[x]+1;
	while(L<R){
        int mid=L+R+1>>1;
        if(b[l[x]+mid-1]<=k)
            L=mid;
        else
            R=mid-1;
    }
	return R;
}
inline int Ask_Rank(int L,int R,int k){
	int A=del[L],B=del[R],sum=0;
	if(A==B){
		for(int i=L;i<=R;++i)
			sum+=(a[i]<=k);
	} else{
		for(int i=L;i<=r[A];++i)
			sum+=(a[i]<=k);
		for(int i=l[B];i<=R;++i)
			sum+=(a[i]<=k);
		for(int i=A+1;i<B;++i)
			sum+=f(i,k);
	}
	return sum;
}
inline int Ask_Num(int l,int r,int k){
	int L=0,R=1e8;
	while(L<R){
		int mid=L+R>>1;
		if(Ask_Rank(l,r,mid)>=k)
			R=mid;
		else
			L=mid+1;
	}
	return R;
}
inline void change(int x,int k){
	int w=del[x];
	a[x]=k;
	for(int i=l[w];i<=r[w];++i)
		b[i]=a[i];
	stable_sort(b+l[w],b+r[w]+1);
}
inline int Ask_Pre(int l,int r,int k){
	if(Ask_Num(l,r,1)>=k)
		return -2147483647;
	int L=1,R=Ask_Rank(l,r,k);
	while(L<R){
		int mid=L+R+1>>1;
		if(Ask_Num(l,r,mid)<k)
			L=mid;
		else
			R=mid-1;
	}
	return Ask_Num(l,r,R);
}
inline int Ask_Nxt(int l,int r,int k){
	if(Ask_Num(l,r,r-l+1)<=k)
		return 2147483647;
	int L=Ask_Rank(l,r,k),R=r-l+1;
	while(L<R){
		int mid=L+R>>1;
		if(Ask_Num(l,r,mid)>k)
			R=mid;
		else
			L=mid+1;
	}
	return Ask_Num(l,r,R);
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		a[i]=b[i]=read();
	len=sqrt(n);
	num=(n+len-1)/len;
	for(int i=1;i<=num;++i){
		l[i]=(i-1)*len+1;
		r[i]=min(n,l[i]+len-1);
		for(int j=l[i];j<=r[i];++j)
			del[j]=i;
		stable_sort(b+l[i],b+r[i]+1);
	}
	for(int i=1;i<=m;++i){
		int opt=read();
		if(opt==1){
			int l=read(),r=read(),k=read();
			printf("%d\n",Ask_Rank(l,r,k));
		} else if(opt==2){
			int l=read(),r=read(),k=read();
			printf("%d\n",Ask_Num(l,r,k));
		} else if(opt==3){
			int pos=read(),k=read();
			change(pos,k);
		} else if(opt==4){
			int l=read(),r=read(),k=read();
			printf("%d\n",Ask_Pre(l,r,k));
		} else{
			int l=read(),r=read(),k=read();
			printf("%d\n",Ask_Nxt(l,r,k));
		}
	}
	return 0;
}