#include<bits/stdc++.h>
#define INF 0x7fffffff
#define endl '\n'
#define PI acos(-1)
#define pb push_back
#define mem(x,v) memset(x,v,sizeof x)
using namespace std;
const int N = 1e5+5;
inline int read(){
	register int x=0,f=1;register char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}

int n,m,tot,a[N];
struct FHQ_Treap{int ls,rs,val,siz,rnd;}t[N*20];
struct FHQ{
	int x,y,z,rt;
	int New(int x){t[++tot]={0,0,x,1,rand()};return tot;}
	void pushup(int u){t[u].siz=t[t[u].ls].siz+t[t[u].rs].siz+1;}
	void split(int u,int k,int &x,int &y){
		if(!u){x=y=0;return;}
		if(t[u].val<=k)x=u,split(t[u].rs,k,t[u].rs,y);
		else y=u,split(t[u].ls,k,x,t[u].ls);
		pushup(u);
	}
	int merge(int x,int y){
		if(!x||!y)return x+y;
		if(t[x].rnd<t[y].rnd){
			t[x].rs=merge(t[x].rs,y);
			pushup(x);return x;
		}
		else{
			t[y].ls=merge(x,t[y].ls);
			pushup(y);return y;
		}
	}
	void insert(int val){
		split(rt,val,x,y);
		rt=merge(merge(x,New(val)),y);
	}
	void del(int val){
		split(rt,val-1,x,y),split(y,val,y,z);
		y=merge(t[y].ls,t[y].rs);
		rt=merge(merge(x,y),z);
	}
	int rnk(int val){
		int x,y,ans;
		split(rt,val-1,x,y);
		ans=t[x].siz+1;
		rt=merge(x,y);
		return ans;
	}
	int kth(int val){
		int u=rt;
		while(u){
			if(val==t[t[u].ls].siz+1)return t[u].val;
			if(val<=t[t[u].ls].siz)u=t[u].ls;
			else val-=t[t[u].ls].siz+1,u=t[u].rs;
		}
	}
	int lst(int val){return kth(rnk(val)-1);}
	int nxt(int val){return kth(rnk(val+1));}
	void build(int l,int r){for(int i=l;i<=r;i++)insert(a[i]);}
};
struct Segment_tree{
	struct Segment{
		int l,r;
		FHQ T;
	}t[N<<2];
	void build(int u,int l,int r){
		t[u].l=l,t[u].r=r,t[u].T.build(l,r);
		if(l==r)return;
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1,mid+1,r);
	}
	int QueryRank(int u,int l,int r,int val){
		if(l<=t[u].l&&t[u].r<=r)return t[u].T.rnk(val)-1;
		int mid=t[u].l+t[u].r>>1,ans=0;
		if(l<=mid)ans+=QueryRank(u<<1,l,r,val);
		if(r>mid)ans+=QueryRank(u<<1|1,l,r,val);
		return ans;
	}
	int QueryKth(int l,int r,int val){
		int L=0,R=1e8,ans=-1;
		while(L<=R){
			int mid=L+R>>1;
			if(QueryRank(1,l,r,mid)+1<=val)L=mid+1,ans=mid;
			else R=mid-1;
		}
		return ans;
	}
	void Modify(int u,int pos,int val){
		t[u].T.del(a[pos]),t[u].T.insert(val);
		if(t[u].l==t[u].r)return;
		int mid=t[u].l+t[u].r>>1;
		if(pos<=mid)Modify(u<<1,pos,val);
		else Modify(u<<1|1,pos,val);
	}
	int Lst(int u,int l,int r,int val){
		if(l<=t[u].l&&t[u].r<=r)return t[u].T.lst(val);
		int mid=t[u].l+t[u].r>>1,ans=-INF;
		if(l<=mid)ans=max(ans,Lst(u<<1,l,r,val));
		if(r>mid) ans=max(ans,Lst(u<<1|1,l,r,val));
		return ans;
	}
	int Nxt(int u,int l,int r,int val){
		if(l<=t[u].l&&t[u].r<=r)return t[u].T.nxt(val);
		int mid=t[u].l+t[u].r>>1,ans=INF;
		if(l<=mid)ans=min(ans,Nxt(u<<1,l,r,val));
		if(r>mid) ans=min(ans,Nxt(u<<1|1,l,r,val));
		return ans;
	}
}T;

signed main(){
//	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	T.build(1,1,n);
	for(int i=1,op,l,r,pos,val;i<=m;i++){
		cin>>op;
		if(op==1)cin>>l>>r>>val,cout<<T.QueryRank(1,l,r,val)+1<<endl;
		if(op==2)cin>>l>>r>>val,cout<<T.QueryKth(l,r,val)<<endl;
		if(op==3)cin>>pos>>val,T.Modify(1,pos,val),a[pos]=val;
		if(op==4)cin>>l>>r>>val,cout<<T.Lst(1,l,r,val)<<endl;
		if(op==5)cin>>l>>r>>val,cout<<T.Nxt(1,l,r,val)<<endl;
	}
	return 0;
}