#include <bits/stdc++.h>
#define LL long long
#define INF 2147483647
#define lowbit(x) (x&-x)
#define mod 1000000007
#define ULL unsigned long long
void write(LL x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
namespace INPUT_SPACE{
	const LL S=(1<<20)+5;char B[S],*H,*T;inline int gc() { if(H==T) T=(H=B)+fread(B,1,S,stdin);return (H==T)?EOF:*H++; }
	inline LL read() { LL x,ch;while((ch=gc())<'0'||ch>'9');x=ch^'0';while((ch=gc())>='0'&&ch<='9') x=x*10+(ch^'0');return x; }
}
using INPUT_SPACE::read;
using namespace std;
const int N=5e4+5;
mt19937 rnd(time(0));
int n,m,a[N];
struct T1{
	int idx,x,y,z;
	struct fhq_treap{
		int ls,rs,sz,key,val;
	}t[N*60];
	inline int get_new(int key){
		t[++idx].key=key;
		t[idx].sz=1;
		t[idx].val=rnd();
		return idx;
	}
	inline void update(int p){
		t[p].sz=t[t[p].ls].sz+t[t[p].rs].sz+1;
	}
	void split(int p,int key,int &x,int &y){
		if(!p) x=y=0;
		else{
			if(t[p].key<=key){
				x=p;
				split(t[p].rs,key,t[p].rs,y);
			}
			else{
				y=p;
				split(t[p].ls,key,x,t[p].ls);
			}
			update(p);
		}
	}
	int merge(int x,int y){
		if(!x || !y) return x|y;
		if(t[x].val>t[y].val){
			t[x].rs=merge(t[x].rs,y);
			update(x);
			return x;
		}
		else{
			t[y].ls=merge(x,t[y].ls);
			update(y);
			return y;
		}
	}
	inline void insert(int &root,int key){
		split(root,key,x,y);
		root=merge(merge(x,get_new(key)),y);
	}
	inline void del(int &root,int key){
		split(root,key,x,z);
		split(x,key-1,x,y);
		y=merge(t[y].ls,t[y].rs);
		root=merge(merge(x,y),z);
	}
	inline int get_pre(int &root,int key){
		split(root,key-1,x,y);
		if(!t[x].sz){
			root=merge(x,y);
			return -INF;
		}
		int p=x;
		while(t[p].rs) p=t[p].rs;
		int ans=t[p].key;
		root=merge(x,y);
		return ans;
	}
	inline int get_next(int &root,int key){
		split(root,key,x,y);
		if(!t[y].sz){
			root=merge(x,y);
			return INF;
		}
		int p=y;
		while(t[p].ls) p=t[p].ls;
		int ans=t[p].key;
		root=merge(x,y);
		return ans;
	}
	inline int get_rank(int &root,int key){
		split(root,key-1,x,y);
		int ans=t[x].sz+1;
		root=merge(x,y);
		return ans;
	}
}tr1;
struct T2{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct seg_tree{
		int l,r,root;
	}t[N<<2];
	void build(int p,int l,int r){
		t[p].l=l,t[p].r=r;
		for(int i=l;i<=r;++i){
			tr1.insert(t[p].root,a[i]);
		}
		if(l==r) return;
		int mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	void change(int p,int x,int k){
		tr1.del(t[p].root,a[x]);
		tr1.insert(t[p].root,k);
		if(t[p].l==t[p].r){
			a[t[p].l]=k;
			return;
		}
		int mid=t[p].l+t[p].r>>1;
		if(x<=mid) change(ls,x,k);
		else change(rs,x,k);
	}
	int get_rank(int p,int l,int r,int key){		//不包括自己
		if(t[p].l>=l && t[p].r<=r){
			return tr1.get_rank(t[p].root,key)-1;
		}
		int mid=t[p].l+t[p].r>>1,ans=0;
		if(l<=mid) ans+=get_rank(ls,l,r,key);
		if(r>mid) ans+=get_rank(rs,l,r,key);
		return ans;
	}
	int get_pre(int p,int l,int r,int key){
		if(t[p].l>=l && t[p].r<=r){
			return tr1.get_pre(t[p].root,key);
		}
		int mid=t[p].l+t[p].r>>1,ans=-INF;
		if(l<=mid) ans=max(ans,get_pre(ls,l,r,key));
		if(r>mid) ans=max(ans,get_pre(rs,l,r,key));
		return ans;
	}
	int get_next(int p,int l,int r,int key){
		if(t[p].l>=l && t[p].r<=r){
			return tr1.get_next(t[p].root,key);
		}
		int mid=t[p].l+t[p].r>>1,ans=INF;
		if(l<=mid) ans=min(ans,get_next(ls,l,r,key));
		if(r>mid) ans=min(ans,get_next(rs,l,r,key));
		return ans;
	}
	inline int get_key(int L,int R,int rank){
		int l=0,r=1e8,ans=0;
		while(l<=r){
			int mid=l+r>>1;
			if(get_rank(1,L,R,mid)+1<=rank) l=mid+1,ans=mid;
			else r=mid-1;
		}
		return ans;
	}
}tr2;
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	freopen("ans.out","w",stdout);
#endif
	n=read(),m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	tr2.build(1,1,n);
	int opt,L,R,K,pos;
	while(m--){
		opt=read();
		if(opt==1){
			L=read(),R=read(),K=read();
			write(tr2.get_rank(1,L,R,K)+1),putchar('\n');
		}
		else if(opt==2){
			L=read(),R=read(),K=read();
			write(tr2.get_key(L,R,K)),putchar('\n');
		}
		else if(opt==3){
			pos=read(),K=read();
			tr2.change(1,pos,K);
		}
		else if(opt==4){
			L=read(),R=read(),K=read();
			write(tr2.get_pre(1,L,R,K)),putchar('\n');
		}
		else if(opt==5){
			L=read(),R=read(),K=read();
			write(tr2.get_next(1,L,R,K)),putchar('\n');
		}
	}
	return 0;
}