#include<iostream>
#include<random>

using namespace std;

#define N 50010
#define INF 2147483647

int n,m;
long long a[N];
struct node{
	int l,r,key,size;
	long long val;
}fhq[N<<6];
int cnt;
mt19937 rnd(210828);
struct Fhq_Treap{
	int root;
	void update(int now) {fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;}
	inline int newnode(long long val)
	{
		fhq[++cnt].size=1,fhq[cnt].val=val,fhq[cnt].key=rnd();
		return cnt;
	}
	inline int merge(int x,int y)
	{
		if(!x||!y) return x+y;
		if(fhq[x].key<fhq[y].key)
		{
			fhq[x].r=merge(fhq[x].r,y),update(x);
			return x;
		}
		fhq[y].l=merge(x,fhq[y].l),update(y);
		return y;
	}
	inline void split(int now,long long val,int &x,int &y)
	{
		if(!now) {x=y=0;return ;}
		if(fhq[now].val<=val)
			x=now,split(fhq[now].r,val,fhq[now].r,y);
		else
			y=now,split(fhq[now].l,val,x,fhq[now].l);
		update(now);
	}
	int x,y,z;
	inline void ins(long long val)
	{
		split(root,val,x,y);
		root=merge(merge(x,newnode(val)),y);
	}
	inline void del(long long val)
	{
		split(root,val,x,z);
		split(x,val-1,x,y);
		y=merge(fhq[y].l,fhq[y].r);
		root=merge(merge(x,y),z);
	}
	inline int get_rank(long long val)
	{
		split(root,val-1,x,y);
		int ans=fhq[x].size+1;
		root=merge(x,y);
		return ans;
	}
	inline long long get_num(int rank)
	{
		int now=root;
		while(now)
		{
			if(fhq[fhq[now].l].size+1==rank)
				break;
			if(fhq[fhq[now].l].size>=rank)
				now=fhq[now].l;
			else
				rank-=fhq[fhq[now].l].size+1,now=fhq[now].r;
		}
		return fhq[now].val;
	}
	inline long long pre(long long val)
	{
		split(root,val-1,x,y);
		long long ans;
		int now=x;
		if(!now)
			ans=-INF;
		else
		{
			while(fhq[now].r)
				now=fhq[now].r;
			ans=fhq[now].val;
		}
		root=merge(x,y);
		return ans;
	}
	inline long long nxt(long long val)
	{
		split(root,val,x,y);
		long long ans;
		int now=y;
		if(!now)
			ans=INF;
		else
		{
			while(fhq[now].l)
				now=fhq[now].l;
			ans=fhq[now].val;
		}
		root=merge(x,y);
		return ans;
	}
	inline void build(int l,int r)
	{
		for(int i=l;i<=r;i++)
			ins(a[i]);
	}
}FT[N<<2];

inline void build(int s,int t,int p)
{
	FT[p].build(s,t);
	if(s==t) return ;
	int mid=(s+t)>>1;
	build(s,mid,p*2),build(mid+1,t,p*2+1);
}
inline int get_rank(int l,int r,int s,int t,int p,long long k)
{
	if(l<=s&&t<=r)
		return FT[p].get_rank(k)-1;
	int mid=(s+t)>>1;
	int rank=0;
	if(l<=mid) rank=get_rank(l,r,s,mid,p*2,k);
	if(r>mid) rank+=get_rank(l,r,mid+1,t,p*2+1,k);
	return rank;
}
inline long long get_num(int l,int r,int rank)
{
	long long L=0,R=1e18,mid;
	while(L<R)
	{
		mid=((L-R)>>1)+R;
		if(get_rank(l,r,1,n,1,mid)+1<=rank)//记得+1为排名
			L=mid+1;
		else
			R=mid;
	}
	return L-1;
}
inline void modify(int k,int s,int t,int p,long long x)
{
	FT[p].del(a[k]),FT[p].ins(x);
	int mid=(s+t)>>1;
	if(s==t) return ;
	if(k<=mid) modify(k,s,mid,p*2,x);
	else modify(k,mid+1,t,p*2+1,x);
}
inline long long pre(int l,int r,int s,int t,int p,long long k)
{
	if(l<=s&&t<=r)
		return FT[p].pre(k);
	int mid=(s+t)>>1;
	long long pr=-INF;
	if(l<=mid) pr=max(pr,pre(l,r,s,mid,p*2,k));
	if(r>mid) pr=max(pr,pre(l,r,mid+1,t,p*2+1,k));
	return pr;
}
inline long long nxt(int l,int r,int s,int t,int p,long long k)
{
	if(l<=s&&t<=r)
		return FT[p].nxt(k);
	int mid=(s+t)>>1;
	long long nx=INF;
	if(l<=mid) nx=min(nx,nxt(l,r,s,mid,p*2,k));
	if(r>mid) nx=min(nx,nxt(l,r,mid+1,t,p*2+1,k));
	return nx;
}

inline long long read(){
	char c=getchar();
	long long ans=0;
	while(!(c>='0'&&c<='9')) c=getchar();
	while(c>='0'&&c<='9')
	{
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans;
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	build(1,n,1);
	while(m--)
	{
		int opt=read(),l=read(),r;
		long long k;
		if(opt==1)
		{
			r=read();
			k=read();
			printf("%d\n",get_rank(l,r,1,n,1,k)+1);
		}
		if(opt==2)
		{
			r=read();
			k=read();
			printf("%lld\n",get_num(l,r,k));
		}
		if(opt==3)
		{
			k=read();
			modify(l,1,n,1,k);
			a[l]=k;
		}
		if(opt==4)
		{
			r=read();
			k=read();
			printf("%lld\n",pre(l,r,1,n,1,k));
		}
		if(opt==5)
		{
			r=read();
			k=read();
			printf("%lld\n",nxt(l,r,1,n,1,k));
		}
	}
	return 0;
}