#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,INF=2147483647;
int n,m,a[N];
int cnt,ls[N<<6],rs[N<<6],val[N<<6],pri[N<<6],siz[N<<6];
struct FHQ_Treap
{
	int root;
	void update(int u)
	{
		siz[u]=siz[ls[u]]+siz[rs[u]]+1;
	}
	int newNode(int x)
	{
		int u=++cnt;
		ls[u]=rs[u]=0;
		val[u]=x;
		pri[u]=rand();
		siz[u]=1;
		return u;
	}
	void spilt(int u,int x,int &L,int &R)
	{
		if(!u)
		{
			L=R=0;
			return;
		}
		if(val[u]<=x)
		{
			L=u;
			spilt(rs[u],x,rs[u],R);
		}
		else
		{
			R=u;
			spilt(ls[u],x,L,ls[u]);
		}
		update(u);
	}
	int merge(int L,int R)
	{
		if(!L||!R) return L|R;
		if(pri[L]>pri[R])
		{
			rs[L]=merge(rs[L],R);
			update(L);
			return L;
		}
		else
		{
			ls[R]=merge(L,ls[R]);
			update(R);
			return R;
		}
	}
	void insert(int x)
	{
		int L,R;
		spilt(root,x,L,R);
		root=merge(merge(L,newNode(x)),R);
	}
	void del(int x)
	{
		int L,R,p;
		spilt(root,x,L,R);
		spilt(L,x-1,L,p);
		root=merge(L,R);
	}
	int kth(int u,int k)
	{
		if(k==siz[ls[u]]+1) return u;
		if(k<=siz[ls[u]]) return kth(ls[u],k);
		if(k>siz[ls[u]]) return kth(rs[u],k-siz[ls[u]]-1);
	}
	int rnk(int x)
	{
		int L,R;
		spilt(root,x-1,L,R);
		int ans=siz[L]+1;
		root=merge(L,R);
		return ans;
	}
	int pre(int x)
	{
		int L,R;
		spilt(root,x-1,L,R);
		int ans;
		if(siz[L]) ans=val[kth(L,siz[L])];
			else ans=-INF;
		root=merge(L,R);
		return ans;
	}
	int nxt(int x)
	{
		int L,R;
		spilt(root,x,L,R);
		int ans;
		if(siz[R]) ans=val[kth(R,1)];
			else ans=INF;
		root=merge(L,R);
		return ans;
	}
}t[N<<2];
#define ls u<<1
#define rs u<<1|1
void build(int u,int l,int r)
{
	for(int i=l;i<=r;i++)
		t[u].insert(a[i]);
	if(l==r) return;
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void update(int u,int l,int r,int x,int k)
{
	t[u].del(a[x]);
	t[u].insert(k);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(x<=mid) update(ls,l,mid,x,k);
		else update(rs,mid+1,r,x,k);
}
int queryrnk(int u,int l,int r,int x,int y,int k)
{
	if(y<l||r<x) return 0;
	if(x<=l&&r<=y) return t[u].rnk(k)-1;
	int mid=(l+r)>>1,res=0;
	if(x<=mid) res+=queryrnk(ls,l,mid,x,y,k);
	if(y>mid) res+=queryrnk(rs,mid+1,r,x,y,k);
	return res;
}
int querykth(int x,int y,int k)
{
	int L=0,R=1e8,ans=-1;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(queryrnk(1,1,n,x,y,mid)+1<=k) ans=mid,L=mid+1;
			else R=mid-1;
	}
	return ans;
}
int querypre(int u,int l,int r,int x,int y,int k)
{
	if(y<l||r<x) return -INF;
	if(x<=l&&r<=y) return t[u].pre(k);
	int mid=(l+r)>>1,res=-INF;
	if(x<=mid) res=max(res,querypre(ls,l,mid,x,y,k));
	if(y>mid) res=max(res,querypre(rs,mid+1,r,x,y,k));
	return res;
}
int querynxt(int u,int l,int r,int x,int y,int k)
{
	if(y<l||r<x) return INF;
	if(x<=l&&r<=y) return t[u].nxt(k);
	int mid=(l+r)>>1,res=INF;
	if(x<=mid) res=min(res,querynxt(ls,l,mid,x,y,k));
	if(y>mid) res=min(res,querynxt(rs,mid+1,r,x,y,k));
	return res;
}
#undef ls
#undef rs
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 opt,x,y,k;
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d%d%d",&x,&y,&k);
			printf("%d\n",queryrnk(1,1,n,x,y,k)+1);
		}
		if(opt==2)
		{
			scanf("%d%d%d",&x,&y,&k);
			printf("%d\n",querykth(x,y,k));
		}
		if(opt==3)
		{
			scanf("%d%d",&x,&k);
			update(1,1,n,x,k);
			a[x]=k;
		}
		if(opt==4)
		{
			scanf("%d%d%d",&x,&y,&k);
			printf("%d\n",querypre(1,1,n,x,y,k));
		}
		if(opt==5)
		{
			scanf("%d%d%d",&x,&y,&k);
			printf("%d\n",querynxt(1,1,n,x,y,k));
		}
	}
	return 0;
}