#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int a[N];
vector<int>block[N];
int L[N],R[N],pos[N];
void rebuild(int x)
{
	block[x].clear();
	for(int i=L[x];i<=R[x];++i)
		block[x].emplace_back(a[i]);
	sort(block[x].begin(),block[x].end());
}
int query_val(int l,int r,int d)
{
	int ans=0,x=pos[l],y=pos[r];
	if(x==y)
	{
		for(int i=l;i<=r;++i)
			if(a[i]<d)
				++ans;
		return ans;
	}
	ans=query_val(l,R[x],d)+query_val(L[y],r,d);
	for(int i=x+1;i<y;++i)
		ans+=lower_bound(block[i].begin(),block[i].end(),d)-block[i].begin();
	return ans+1;
}
int query_rank(int l,int r,int k)
{
	int L=-1,R=1e8+1;
	while(L+1<R)
	{
		int mid=L+R>>1;
		if(query_val(l,r,mid)<=k)
			L=mid;
		else
			R=mid; 
	}
	return L;
}
void update(int x,int d)
{
	int k=pos[x];
	a[x]=d;
	rebuild(k);
} 
int query_pre(int l,int r,int d)
{
	int x=pos[l],y=pos[r],ans=-2147483647;
	if(x==y)
	{
		for(int i=l;i<=r;++i)
			if(a[i]<d)
				ans=max(ans,a[i]);
		return ans;
	}
	ans=max(query_pre(l,R[x],d),query_pre(L[y],r,d));
	for(int i=x+1;i<y;++i)
	{
		int k=lower_bound(block[i].begin(),block[i].end(),d)-block[i].begin();
		if(k>0)ans=max(ans,block[i][k-1]);
	}
	return ans;
}
int query_nxt(int l,int r,int d)
{
	int x=pos[l],y=pos[r],ans=2147483647;
	if(x==y)
	{
		for(int i=l;i<=r;++i)
			if(a[i]>d)
				ans=min(ans,a[i]);
		return ans;
	}
	ans=min(query_nxt(l,R[x],d),query_nxt(L[y],r,d));
	for(int i=x+1;i<y;++i)
	{
		int k=upper_bound(block[i].begin(),block[i].end(),d)-block[i].begin();
		if(k<block[i].size())
			ans=min(ans,block[i][k]);
	}
	return ans;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); 
	int n,m;
	cin>>n>>m;
	int t=sqrt(n);
	for(int i=1;i<=t;++i)
	{
		L[i]=(i-1)*t+1;
		R[i]=i*t;
	}
	if(R[t]<n)
	{
		++t;
		L[t]=R[t-1]+1;
		R[t]=n;
	}
	for(int i=1;i<=n;++i)
		for(int j=L[i];j<=R[i];++j)
			pos[j]=i;
	for(int i=1;i<=n;++i)
	{
		int val;
		cin>>val;
		update(i,val);
	}
	while(m--)
	{
		int op,l,r,k;
		cin>>op>>l;
		if(op==1)
		{
			cin>>r>>k;
			cout<<query_val(l,r,k)<<'\n';
		}
		if(op==2)
		{
			cin>>r>>k;
			cout<<query_rank(l,r,k)<<'\n';
		}
		if(op==3)
		{
			cin>>k;
			update(l,k);
		}
		if(op==4)
		{
			cin>>r>>k;
			cout<<query_pre(l,r,k)<<'\n';
		}
		if(op==5)
		{
			cin>>r>>k;
			cout<<query_nxt(l,r,k)<<'\n';
		}
	}
}

WA+tle 20pts