#include<bits/stdc++.h>
#define inf 2147483647
using namespace std;
const int N=50010;
int n,m;
int a[N];
int ch[N*50][2],val[N*50],key[N*50],sz[N*50],idx;
struct nd{
	int l,r;
	int root;
}tr[N*4];
int new_node(int v){
	val[++idx]=v;
	key[idx]=rand();
	sz[idx]=1;
	return idx;
}
void pushup(int u){
	sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1;
}
void split(int u,int &x,int &y,int k){
	if(!u){
		x=y=0;
		return;
	}
	if(val[u]<=k){
		x=u;
		split(ch[u][1],ch[x][1],y,k);
		pushup(x);
	}else{
		y=u;
		split(ch[u][0],x,ch[y][0],k);
		pushup(y);
	}
}
int merge(int x,int y){
	if(!x||!y){
		return x+y;
	}
	if(key[x]<=key[y]){
		ch[x][1]=merge(ch[x][1],y);
		pushup(x);
		return x;
	}else{
		ch[y][0]=merge(x,ch[y][0]);
		pushup(y);
		return y;
	}
}
void insert(int &root,int a){
	int x,y;
	split(root,x,y,a);
	root=merge(merge(x,new_node(a)),y);
}
void del(int &root,int a){
	int x,y,z;
	split(root,y,z,a);
	split(y,x,y,a-1);
	y=merge(ch[y][0],ch[y][1]);
	root=merge(merge(x,y),z);
}
int get_rank(int &root,int a){
	int x,y;
	split(root,x,y,a-1);
	int t=sz[x];
	root=merge(x,y);
	return t;
}
int get_lower(int &root,int a){
	int res=-inf;
	int u=root;
	while(u){
		if(a>val[u]){
			res=max(res,val[u]);
			u=ch[u][1];
		}else{
			u=ch[u][0];
		}
	}
	return res;
}
int get_upper(int &root,int a){
	int res=inf;
	int u=root;
	while(u){
		if(a<val[u]){
			res=min(res,val[u]);
			u=ch[u][0];
		}else{
			u=ch[u][1];
		}
	}
	return res;
}
void build(int u,int l,int r){
	tr[u]={l,r};
	for(int i=l;i<=r;i++){
		insert(tr[u].root,a[i]);
	}
	if(l==r) return;
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
int query_rank(int u,int l,int r,int k){
	if(l<=tr[u].l&&tr[u].r<=r){
		return get_rank(tr[u].root,k);
	}
	int mid=tr[u].l+tr[u].r>>1;
	int res=0;
	if(l<=mid) res+=query_rank(u<<1,l,r,k);
	if(r>mid) res+=query_rank(u<<1|1,l,r,k);
	return res; 
}
void update(int u,int x,int k){
	del(tr[u].root,a[x]);
	insert(tr[u].root,k);
	if(tr[u].l==tr[u].r) return;
	int mid=tr[u].l+tr[u].r>>1;
	if(x<=mid) update(u<<1,x,k);
	else update(u<<1|1,x,k);
}
int query_lower(int u,int l,int r,int k){
	if(l<=tr[u].l&&tr[u].r<=r){
		return get_lower(tr[u].root,k);
	}
	int mid=tr[u].l+tr[u].r>>1;
	int res=-inf;
	if(l<=mid) res=max(res,query_lower(u<<1,l,r,k));
	if(r>mid) res=max(res,query_lower(u<<1|1,l,r,k));
	return res;
}
int query_upper(int u,int l,int r,int k){
	if(l<=tr[u].l&&tr[u].r<=r){
		return get_upper(tr[u].root,k);
	}
	int mid=tr[u].l+tr[u].r>>1;
	int res=inf;
	if(l<=mid) res=min(res,query_upper(u<<1,l,r,k));
	if(r>mid) res=min(res,query_upper(u<<1|1,l,r,k));
	return res;
}
int main(){
	srand(time(0));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	while(m--){
		int op,x,l,r,k;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",query_rank(1,l,r,k)+1);
		}else if(op==2){
			scanf("%d%d%d",&l,&r,&k);	
			int left=0,right=1e8;
			while(left<right){
				int mid=left+right+1>>1;
				if(query_rank(1,l,r,mid)+1<=k) left=mid;
				else right=mid-1;
			}
			printf("%d\n",left);
		}else if(op==3){
			scanf("%d%d",&x,&k);
			update(1,x,k);
			a[x]=k;
		}else if(op==4){
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",query_lower(1,l,r,k));
		}else{
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",query_upper(1,l,r,k));
		}
	}
	return 0;
}