#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<cstdio>
#define in inline
#define rg register
#define ll long long
using namespace std;
struct SPLAY{
	ll l,r,fa,val,chong,siz;
}tr[2000010];
ll dians;
struct TREE{
	ll l,r,root;
}tree[200010];
ll n,m,a[100010],on[2000010];
ll opt,l,r,k,K,ans,end,Ans;
ll MAXN;
ll L,R,mid,wen;
in ll max(ll ,ll );
in ll min(ll ,ll );
in void ins(ll ,ll );
in void updata(ll );
in void rot(ll ,ll );
in void splay(ll ,ll ,ll );
in ll pre(ll ,ll );
in ll nxt(ll ,ll );
in ll rank(ll ,ll );
in void shan(ll ,ll );
in void build_tree(ll ,ll ,ll );
in void change(ll );
in void ask(ll );
int main(){
	scanf("%lld %lld",&n,&m);
	for( ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		MAXN=max(a[i],MAXN); 
	}
	build_tree(1,1,n);
	for( ll i=1;i<=m;i++){
		wen++;
		scanf("%lld",&opt);
		if(opt==1){
			scanf("%lld %lld %lld",&l,&r,&k);
			ans=0;
			ask(1);
			printf("%lld\n",ans+1);
		}else if(opt==2){
			scanf("%lld %lld %lld",&l,&r,&K);
			Ans=0;
			L=1,R=MAXN+1;
			while(L<=R){
				mid=(L+R)/2;
				ans=-2147483647;
				k=mid;
				opt=4;
				ask(1);
				if(ans<0){
					L=mid+1;
				}
				k=ans;
				opt=2;
				end=ans=0;
				ask(1);
				end+=ans;
				ans++;
				if(K<ans){
					R=mid-1;
				}else if(K>end){
					L=mid+1;
				}else{
					Ans=k;
					break;
				}
			}
			printf("%lld\n",Ans);
		}else if(opt==3){
			scanf("%lld %lld",&l,&k);
			MAXN=max(k,MAXN);
			change(1);
			a[l]=k;
		}else if(opt==4){
			scanf("%lld %lld %lld",&l,&r,&k);
			ans=-2147483647;
			ask(1);
			printf("%lld\n",ans);
		}else if(opt==5){
			scanf("%lld %lld %lld",&l,&r,&k);
			ans=2147483647;
			ask(1);
			printf("%lld\n",ans);
		}
	}
	return 0;
}
in void ask(ll hao){
	if(tree[hao].l>=l&&tree[hao].r<=r){
		if(opt<=2){
			ans+=rank(hao,k);
		}else if(opt==4){
			ll dian=pre(hao,k);
			if(dian==0)return;
			ans=max(tr[dian].val,ans);
		}else if(opt==5){
			ll dian=nxt(hao,k);
			if(dian==0)return;
			ans=min(tr[dian].val,ans);
		}
		return;
	}
	ll mid=(tree[hao].l+tree[hao].r)/2;
	if(l<=mid){
		ask(hao*2);
	}if(r>mid){
		ask(hao*2+1);
	}
	return;
}
in void change(ll hao){
	ins(hao,k);
	shan(hao,a[l]);
	if(tree[hao].l==tree[hao].r){
		return;
	}
	ll mid=(tree[hao].l+tree[hao].r)/2;
	if(l<=mid){
		change(hao*2);
	}else{
		change(hao*2+1);
	}
	return;
}
in void shan(ll root,ll val){
	ll pr=pre(root,val),nx=nxt(root,val);
	ll dian;
	if(pr!=0&&nx!=0){
		splay(root,pr,0);
		splay(root,nx,pr);
		dian=tr[nx].l;
		if(tr[dian].chong>1){
			tr[dian].chong--;
		}else{
			tr[dian].fa=tr[dian].l=tr[dian].r=tr[dian].chong=tr[dian].siz=tr[dian].val=0;
			tr[nx].l=0;
		}
	}else if(pr==0){
		splay(root,nx,0);
		dian=tr[nx].l;
		if(tr[dian].chong>1){
			tr[dian].chong--;
		}else{
			tr[dian].fa=tr[dian].l=tr[dian].r=tr[dian].chong=tr[dian].siz=tr[dian].val=0;
			tr[nx].l=0;
		}
	}else if(nx==0){
		splay(root,pr,0);
		dian=tr[pr].r;
		if(tr[dian].chong>1){
			tr[dian].chong--;
		}else{
			tr[dian].fa=tr[dian].l=tr[dian].r=tr[dian].chong=tr[dian].siz=tr[dian].val=0;
			tr[pr].r=0;
		}
	}
	updata(dian);
	updata(nx);
	updata(pr);
	return;
}
in ll pre(ll root,ll val){
	ll dian=tree[root].root;
	ll cnt=-(0x7fffffff),hao=0;
	while(dian!=0){
		if(tr[dian].val>val){
			dian=tr[dian].l;
		}else if(tr[dian].val<val){
			if(tr[dian].val>cnt){
				cnt=tr[dian].val;
				hao=dian;
			}
			dian=tr[dian].r;
		}else{
			dian=tr[dian].l;
			while(dian!=0){
				if(tr[dian].val>cnt){
					cnt=tr[dian].val;
					hao=dian;
				}
				dian=tr[dian].r;
			}
		}
	}
	return hao;
}
in ll nxt(ll root,ll val){
	ll dian=tree[root].root;
	ll cnt=0x7fffffff,hao=0;
	while(dian!=0){
		if(tr[dian].val>val){
			if(tr[dian].val<cnt){
				cnt=tr[dian].val;
				hao=dian;
			} 
			dian=tr[dian].l;
		}else if(tr[dian].val<val){
			dian=tr[dian].r;
		}else{
			dian=tr[dian].r;
			while(dian!=0){
				if(tr[dian].val<cnt){
					cnt=tr[dian].val;
					hao=dian;
				}
				dian=tr[dian].l;
			}
		}
	}
	return hao;
}
in ll rank(ll root,ll val){
	ll dian=tree[root].root;
	ll cun=0;
	while(dian!=0){
		if(tr[dian].val>val){
			dian=tr[dian].l;
		}else if(tr[dian].val==val){
			cun+=tr[tr[dian].l].siz;
			end+=tr[dian].chong;
			break;
		}else{
			cun+=tr[tr[dian].l].siz+tr[dian].chong;
			dian=tr[dian].r;
		}
	}
	return cun;
}
in void ins(ll root,ll val){
	ll dian=tree[root].root;
	while(dian!=0){
		tr[dian].siz++;
		if(tr[dian].val>val){
			if(!tr[dian].l){
				dians++;
				tr[dian].l=dians;
				tr[dians].fa=dian;
				tr[dians].l=tr[dians].r=0;
				tr[dians].val=val;
				tr[dians].chong=tr[dians].siz=1;
				on[dians]=root;
				splay(root,dians,0);
				break;
			}else{
				dian=tr[dian].l;
			}
		}else if(tr[dian].val<val){
			if(!tr[dian].r){
				dians++;
				tr[dian].r=dians;
				tr[dians].fa=dian;
				tr[dians].l=tr[dians].r=0;
				tr[dians].val=val;
				tr[dians].chong=tr[dians].siz=1;
				on[dians]=root;
				splay(root,dians,0);
				break;
			}else{
				dian=tr[dian].r;
			}
		}else{
			tr[dian].chong++;
			splay(root,dian,0);
			break;
		}
	}
	return;
}
in void splay(ll root,ll dian,ll to){
	if(dian==to)return;
	ll A,B;
	ll fa=tr[dian].fa;
	ll gr=tr[fa].fa;
	while(fa!=to&&gr!=to&&dian!=0){
		A=B=0;
		if(tr[gr].r==fa)A=1;
		if(tr[fa].r==dian)B=1;
		if(A==B)rot(root,fa);
		else rot(root,dian);
		rot(root,dian);
		fa=tr[dian].fa;
		gr=tr[fa].fa;
	}
	if(fa!=to)rot(root,dian);
	return;
}
in void rot(ll root,ll dian){
	ll fa,gr;
	fa=tr[dian].fa;
	gr=tr[fa].fa;
	if(dian==0)return;
	if(tr[fa].l==dian){
		tr[tr[dian].r].fa=fa;
		tr[fa].l=tr[dian].r;
		tr[dian].r=fa;
	}else{
		tr[tr[dian].l].fa=fa;
		tr[fa].r=tr[dian].l;
		tr[dian].l=fa;
	}	
	tr[fa].fa=dian;
	updata(fa);
	updata(dian);
	tr[dian].fa=gr;
	if(tree[root].root==fa){
		tree[root].root=dian;
	}
	if(!gr)return;
	if(tr[gr].l==fa){
		tr[gr].l=dian;
	}else if(tr[gr].r==fa){
		tr[gr].r=dian;
	}
	return;
}
in void updata(ll dian){
	tr[dian].siz=tr[tr[dian].l].siz+tr[tr[dian].r].siz+tr[dian].chong;
	return;
}
in void build_tree(ll hao,ll l,ll r){
	tree[hao].root=0;
	tree[hao].l=l;
	tree[hao].r=r;
	if(l==r){
		ll dian=hao;
		while(dian>0){
			if(tree[dian].root==0){
				tree[dian].root=++dians;
				tr[dians].chong=tr[dians].siz=1;
				tr[dians].val=a[l];
				tr[dians].l=tr[dians].r=tr[dians].fa=0;
				on[dians]=dian;
			}else{
				ins(dian,a[l]);
			}
			dian/=2;
		}
		return;
	} 
	ll mid=(l+r)/2;
	build_tree(hao*2,l,mid);
	build_tree(hao*2+1,mid+1,r);
	return;
}
in ll max(ll A,ll B){
	return A>B?A:B;
}
in ll min(ll A,ll B){
	return A<B?A:B;
}