#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[114514];
struct fhq
{
	struct node
	{
		int val,rnd,size;
		node *l,*r;
	};
	node *root=NULL;
	void update(node *p)
	{
		if(p==NULL)
			return;
		p->size=1;
		if(p->l!=NULL)
			p->size+=p->l->size;
		if(p->r!=NULL)
			p->size+=p->r->size;
	}
	node *New(int x)
	{
		node *p=new node;
		p->val=x;
		p->rnd=rand();
		p->size=1;
		p->l=p->r=NULL;
		return p;
	}
	node *merge(node *x,node *y)	
	{	
		if(x==NULL)
			return y;
		if(y==NULL)
			return x;
		if(x->rnd<=y->rnd)
		{
			x->r=merge(x->r,y);
			update(x);
			return x;
		}
		else
		{
			y->l=merge(x,y->l);
			update(y);
			return y;
		}
	}
	void split(node *p,int val,node *&x,node *&y)
	{
		if(p==NULL)
			x=y=NULL;
		else
		{
			if(p->val<=val)
			{
				x=p;
				split(p->r,val,p->r,y);
			}
			else
			{
				y=p;
				split(p->l,val,x,p->l);
			}
			update(p);
		}
	}
	void insert(int x)
	{
		node *a=NULL,*b=NULL;
		split(root,x,a,b);
		root=merge(merge(a,New(x)),b);
	}
	int Rank(int x)
	{
		node *a=NULL,*b=NULL;
		split(root,x-1,a,b);
		int ans=a?a->size+1:1;
		root=merge(a,b);	
		return ans;
	}
	int num(int x)
	{
		node *p=root;
		while(p!=NULL)
		{
			int ls=0;
			if(p->l) 
				ls=p->l->size;
			if(ls+1==x)
				break;
			else if(ls+1<x)
				x-=ls+1,p=p->r;
			else
				p=p->l;
		}
		return p->val;
	}
	void del(int x)
	{
		node *a=NULL,*b=NULL,*c=NULL;
		split(root,x,b,c);
		split(b,x-1,a,b);
		node *tmp1,*tmp2;
		if(!b) 
			tmp2=a;
		else
		{
			tmp1=merge(b->l,b->r),tmp2=merge(a,tmp1);
			if(b) 
				delete b;
		}
		root=merge(tmp2,c);
	}
	int pre(int x)
	{
		int ans;
		node *a=NULL,*b=NULL;
		split(root,x-1,a,b);
		node *p=a;
		if(a==NULL)
		{
			root=merge(a,b);
			return -INT_MAX;
		}
		while(p!=NULL)
			ans=p->val,p=p->r;
		root=merge(a,b);
		return ans;
	}
	int nxt(int x)	
	{
		int ans;
		node *a=NULL,*b=NULL;
		split(root,x,a,b);
		node *p=b;
		if(b==NULL)
		{
			root=merge(a,b);
			return INT_MAX;
		}
		while(p!=NULL)
			ans=p->val,p=p->l;
		root=merge(a,b);
		return ans;
	}
};
#define ls root*2
#define rs root*2+1
#define mid (t[root].l+t[root].r)/2
struct smt
{
	int l,r;
	fhq ft;
}t[114514*4];
void bld(int l,int r,int root)
{
	t[root].l=l;
	t[root].r=r;
	for(int i=l;i<=r;i++)
		t[root].ft.insert(a[i]);
	if(l==r)
		return;
	bld(l,mid,ls);
	bld(mid+1,r,rs);
}
int qrank(int x,int y,int root,int k)
{
	if(x<=t[root].l&&t[root].r<=y)
		return t[root].ft.Rank(k)-1;
	int res=0;
	if(x<=mid)
		res+=qrank(x,y,ls,k);
	if(y>mid)
		res+=qrank(x,y,rs,k);
	return res;
}
int qnum(int x,int y,int k)
{
	int l=0,r=1e8,ans=0;
	while(l<=r)
	{
		int Mid=(l+r)/2;
		if(qrank(x,y,1,Mid)<k)
			ans=Mid,l=Mid+1;
		else
			r=Mid-1;
	}
	return ans;
}
void add(int root,int k,int now)
{
	t[root].ft.del(a[k]);
	t[root].ft.insert(now);
	if(t[root].l==t[root].r)
		return;
	if(k<=mid)
		add(ls,k,now);
	else
		add(rs,k,now);
}
int qpre(int x,int y,int root,int k)
{
	if(t[root].l>=x&&t[root].r<=y)
		return t[root].ft.pre(k);
	int ans=-INT_MAX;
	if(x<=mid)
		ans=max(ans,qpre(x,y,ls,k));
	if(y>mid)
		ans=max(ans,qpre(x,y,rs,k));
	return ans;
}
int qnxt(int x,int y,int root,int k)
{
	if(x<=t[root].l&&t[root].r<=y)	
		return t[root].ft.nxt(k);
	int ans=INT_MAX;
	if(x<=mid)
		ans=min(ans,qnxt(x,y,ls,k));
	if(y>mid)
		ans=min(ans,qnxt(x,y,rs,k));
	return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	bld(1,n,1);
	while(m--)
	{
		int op,l,r,k;
		cin>>op;
		if(op==1)
		{
			cin>>l>>r>>k;
			cout<<qrank(l,r,1,k)<<endl;
		}
		else if(op==2)
		{
			cin>>l>>r>>k;
			cout<<qnum(l,r,k)<<endl;
		}
		else if(op==3)
		{
			int p;
			cin>>p>>k;
			add(1,p,k);
		}
		else if(op==4)
		{
			cin>>l>>r>>k;
			cout<<qpre(l,r,1,k)<<endl;
		}
		else
		{
			cin>>l>>r>>k;
			cout<<qnxt(l,r,1,k)<<endl;
		}
	}
}