#include<cstdio>#include<algorithm>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#define N 50010#define INF 2147483647using namespace std;using namespace __gnu_pbds;typedef pair<int,int> Point;typedef tree<Point,null_type,less<Point>,rb_tree_tag,tree_order_statistics_node_update> rb_tree;typedef rb_tree::iterator ITER;rb_tree T[N<<2];int a[N],tags[N],tag,n,m;void buildtree(int rt,int l,int r){	if(l==r)	  {	  	T[rt].insert(Point(a[l],l));	  	return;	  }	int m=(l+r>>1);	buildtree(rt<<1,l,m);	buildtree(rt<<1|1,m+1,r);	T[rt]=T[rt<<1];	for(ITER it=T[rt<<1|1].begin();it!=T[rt<<1|1].end();++it)	  T[rt].insert(*it);}int Rank(int v,int TAG,int ql,int qr,int rt,int l,int r){	if(ql<=l&&r<=qr)	  return T[rt].order_of_key(Point(v,TAG));	int m=(l+r>>1),res=0;	if(ql<=m) res+=Rank(v,TAG,ql,qr,rt<<1,l,m);	if(m<qr) res+=Rank(v,TAG,ql,qr,rt<<1|1,m+1,r);	return res;}int Pre(int v,int ql,int qr,int rt,int l,int r){	if(ql<=l&&r<=qr)	  {	  	ITER it=T[rt].lower_bound(Point(v,0));	  	if(it==T[rt].begin()) return -INF;		--it;	  	return (*it).first;	  }	int m=(l+r>>1),res=-INF;	if(ql<=m) res=max(res,Pre(v,ql,qr,rt<<1,l,m));	if(m<qr) res=max(res,Pre(v,ql,qr,rt<<1|1,m+1,r));	return res;}int Nex(int v,int ql,int qr,int rt,int l,int r){	if(ql<=l&&r<=qr)	  {	  	ITER it=T[rt].upper_bound(Point(v,INF));	  	if(it==T[rt].end())		  return INF;	  	return (*it).first;	  }	int m=(l+r>>1),res=INF;	if(ql<=m) res=min(res,Nex(v,ql,qr,rt<<1,l,m));	if(m<qr) res=min(res,Nex(v,ql,qr,rt<<1|1,m+1,r));	return res;}void Update(int p,int v,int rt,int l,int r){	T[rt].erase(Point(a[p],tags[p]));	T[rt].insert(Point(v,tag));	if(l==r) return;	int m=(l+r>>1);	if(p<=m) Update(p,v,rt<<1,l,m);	else Update(p,v,rt<<1|1,m+1,r);}int Kth(int K,int ql,int qr){	int l=0,r=100000000;	while(l<r)	  {	  	int m=(l+r>>1);	  	if(Rank(m,INF,ql,qr,1,1,n)>=K)	  	  r=m;	  	else	  	  l=m+1;	  }	return l;}int main(){//	freopen("bzoj3196.in","r",stdin);	int op,x,y,z;	scanf("%d%d",&n,&m);	for(int i=1;i<=n;++i)	  {	  	scanf("%d",&a[i]);	  	tags[i]=i;	  }	tag=n;	buildtree(1,1,n);//	for(int i=1;i<=n*4;++i)//	  printf("%d ",(*T[i].begin()).second);//	puts("");	for(;m;--m)	  {	  	scanf("%d%d%d",&op,&x,&y);	  	if(op==1)	  	  {	  	  	scanf("%d",&z);	  	  	printf("%d\n",Rank(z,0,x,y,1,1,n)+1);	  	  }	  	else if(op==2)	  	  {	  	  	scanf("%d",&z);	  	  	printf("%d\n",Kth(z,x,y));	  	  }	  	else if(op==3)	  	  {	  	  	++tag;	  	  	Update(x,y,1,1,n);	  	  	a[x]=y;	  	  	tags[x]=tag;	  	  }	  	else if(op==4)	  	  {	  	  	scanf("%d",&z);	  	  	printf("%d\n",Pre(z,x,y,1,1,n));	  	  }	  	else	  	  {	  	  	scanf("%d",&z);	  	  	printf("%d\n",Nex(z,x,y,1,1,n));	  	  }	  }	return 0;}