#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int res=0;
	bool zf=0;
	char c;
	while(((c=getchar())<'0'||c>'9')&&c!='-');
	if(c=='-')zf=1;
	else res=c-'0';
	while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
	return (zf?-res:res);
}
class fhqTreap{
	private:
		#define maxn 50005
		#define maxNode 800005
		struct Node{
			int l,r;
			int val,key;
			int size;
		}node[maxNode<<4];
		int root[maxn<<2];
		int cnt;
		inline int newnode(const int val){
			node[++cnt].val=val;
			node[cnt].key=rand();
			node[cnt].size=1;
			return cnt;
		}
		inline void update(const int now){
			node[now].size=node[node[now].l].size+node[node[now].r].size+1;
			return;
		}
		void split(int now,const int val,int &x,int &y){
			if(!now)x=y=0;
			else{
				if(node[now].val<=val){
					x=now;
					split(node[now].r,val,node[x].r,y);
				}
				else{
					y=now;
					split(node[now].l,val,x,node[y].l);
				}
				update(now);
			}
			return;
		}
		int merge(int x,int y){
			if(!x||!y)return x+y;
			if(node[x].key<node[y].key){
				node[x].r=merge(node[x].r,y);
				update(x);
				return x;
			}
			else{
				node[y].l=merge(x,node[y].l);
				update(y);
				return y;
			}
		}
	public:
		int x,y,z;
		inline void ins(const int which,const int val){
			split(root[which],val,x,y);
			root[which]=merge(merge(x,newnode(val)),y);
			return;
		}
		inline void del(const int which,const int val){
			split(root[which],val-1,x,y);
			split(y,val,y,z);
			y=merge(node[y].l,node[y].r);
			root[which]=merge(merge(x,y),z);
			return;
		}
		inline int getrank(const int which,const int val){
			split(root[which],val-1,x,y);
			int res=node[x].size;
			root[which]=merge(x,y);
			return res;
		}
		inline int getnum(const int which,int rank){
			int now=root[which];
			while(1){
				if(node[node[now].l].size+1==rank)return node[now].val;
				if(node[node[now].l].size+1>rank)now=node[now].l;
				else rank-=node[node[now].l].size+1,now=node[now].r;
			}
		}
		inline int getpre(const int which,const int val){
			split(root[which],val-1,x,y);
			int now=x;
			if(!now)return -2147483647;
			while(node[now].r)now=node[now].r;
			int res=node[now].val;
			root[which]=merge(x,y);
			return res;
		}
		inline int getnxt(const int which,const int val){
			split(root[which],val,x,y);
			int now=y;
			if(!now)return 2147483647;
			while(node[now].l)now=node[now].l;
			int res=node[now].val;
			root[which]=merge(x,y);
			return res;
		}
};
int n,data[maxn];
class segment{
	private:
		fhqTreap node;
	public:
		void build(const int k,const int l,const int r){
			if(l==r){
				node.ins(k,data[l]);
				return;
			}
			for(register int i=l;i<=r;i++)node.ins(k,data[i]);
			int mid=(l+r)>>1;
			build(k<<1,l,mid);build(k<<1|1,mid+1,r);
			return;
		}
		void modify(const int k,const int l,const int r,const int pos,const int val){
			if(l>pos||r<pos)return;
			if(l==r){
				node.del(k,data[l]);
				node.ins(k,val);
				return;
			} 
			node.del(k,data[l]);
			node.ins(k,val);
			int mid=(l+r)>>1;
			modify(k<<1,l,mid,pos,val);modify(k<<1|1,mid+1,r,pos,val);
			return;
		}
		int queryrank(const int k,const int x,const int y,const int l,const int r,const int val){
			if(x>r||y<l)return 0;
			if(x>=l&&y<=r){
				return node.getrank(k,val);
			}
			int mid=(x+y)>>1;
			return queryrank(k<<1,x,mid,l,r,val)+queryrank(k<<1|1,mid+1,y,l,r,val);
		}
		#define maxnum 100000005
		inline int querynum(const int l,const int r,const int rank){
			int L=1,R=maxnum,ans;
			while(L<=R){
				int mid=(L+R)>>1;
				if(queryrank(1,1,n,l,r,mid)+1<=rank)ans=mid,L=mid+1;
				else R=mid-1;
			}
			return ans;
		}
		int querypre(const int k,const int x,const int y,const int l,const int r,const int val){
			if(x>r||y<l)return -2147483647;
			if(x>=l&&y<=r)return node.getpre(k,val);
			int mid=(x+y)>>1;
			return max(querypre(k<<1,x,mid,l,r,val),querypre(k<<1|1,mid+1,y,l,r,val));
		}
		int querynxt(const int k,const int x,const int y,const int l,const int r,const int val){
			if(x>r||y<l)return 2147483647;
			if(x>=l&&y<=r)return node.getnxt(k,val);
			int mid=(x+y)>>1;
			return min(querynxt(k<<1,x,mid,l,r,val),querynxt(k<<1|1,mid+1,y,l,r,val));
		}
};
segment sts;
signed main(){
	n=read();int m=read();
	for(register int i=1;i<=n;i++)data[i]=read();
	sts.build(1,1,n);
	while(m--){
		int opt=read();
		switch(opt){
			case 1:{
				int l=read(),r=read(),val=read();
				cout<<sts.queryrank(1,1,n,l,r,val)+1<<'\n';
				break;
			}
			case 2:{
				int l=read(),r=read(),rank=read();
				cout<<sts.querynum(l,r,rank)<<'\n';
				break;
			}
			case 3:{
				int pos=read(),val=read();
				sts.modify(1,1,n,pos,val);
				data[pos]=val;
				break;
			}
			case 4:{
				int l=read(),r=read(),val=read();
				cout<<sts.querypre(1,1,n,l,r,val)<<'\n';
				break;
			}
			case 5:{
				int l=read(),r=read(),val=read();
				cout<<sts.querynxt(1,1,n,l,r,val)<<'\n';
				break;
			}
		}
	}
	return 0;
}