#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
    int t=0;bool sign=false;char c=getchar();
    while(!isdigit(c)){sign|=c=='-';c=getchar();}
    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
    return sign?-t:t;
}
inline LL read_LL(){
    LL t=0;bool sign=false;char c=getchar();
    while(!isdigit(c)){sign|=c=='-';c=getchar();}
    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
    return sign?-t:t;
}
inline char get_char(){
    char c=getchar();
    while(c==' '||c=='\n'||c=='\r')c=getchar();
    return c;
}
inline void write(LL x){
    register char c[21],len=0;
    if(!x)return putchar('0'),void();
    if(x<0)x=-x,putchar('-');
    while(x)c[++len]=x%10,x/=10;
    while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=(5e4+5)*4,MAXS=MAXN*20,Inf=0x7fffffff;
template <typename T>
struct Treap{
	int pool[MAXS],top,tot;
	int root[MAXN],ch[MAXS][2],r[MAXS],sz[MAXS],cnt[MAXS];
	T val[MAXS];
	int new_node(T v){
		int id=top?pool[top--]:++tot;
		val[id]=v;r[id]=rand();sz[id]=cnt[id]=1;ch[id][0]=ch[id][1]=0;
		return id;
	}
	void push_up(int id){sz[id]=sz[ch[id][0]]+sz[ch[id][1]]+cnt[id];}
	void Rotate(int &id,int dir){
		int t=ch[id][dir^1];
		ch[id][dir^1]=ch[t][dir];ch[t][dir]=id;id=t;
		push_up(ch[id][dir]);push_up(id);
	}
	void Insert(int &id,T v){
		if(!id)
		return id=new_node(v),void();
		if(v==val[id])
		cnt[id]++;
		else{
			int dir=v<val[id]?0:1;
			Insert(ch[id][dir],v);
			if(r[id]<r[ch[id][dir]])
			Rotate(id,dir^1);
		}
		push_up(id);
	}
	void Erase(int &id,T v){
		if(!id)
		return;
		if(v==val[id]){
			if(cnt[id]>1)return	cnt[id]--,push_up(id);
			else if(!ch[id][0])pool[++top]=id,id=ch[id][1];
			else if(!ch[id][1])pool[++top]=id,id=ch[id][0];
			else{
				int d=r[ch[id][0]]>r[ch[id][1]]?1:0;
				Rotate(id,d);Erase(ch[id][d],v);push_up(id);
			}
		}
		else{
			if(v<val[id])Erase(ch[id][0],v);
			else Erase(ch[id][1],v);
			push_up(id);
		}
	}
	int Rank(int id,T v){//有多少个数严格小于v 
		if(!id)return 0;
		if(v==val[id])return sz[ch[id][0]];
		else if(v<val[id])return Rank(ch[id][0],v);
		else return sz[ch[id][0]]+cnt[id]+Rank(ch[id][1],v);
	}
	T Kth(int id,int rk){
		if(!id) return -1;//第rk小的节点不存在 
		if(rk>sz[ch[id][0]]+cnt[id]) return Kth(ch[id][1],rk-sz[ch[id][0]]-cnt[id]);
		else if(rk>sz[ch[id][0]]) return val[id];
		else return Kth(ch[id][0],rk);
	}
	T Pre(int id,T v){
		int pos=id,ans=-Inf;
		while(pos){
			if(val[pos]<v){
				ans=ans<val[pos]?val[pos]:ans;
				pos=ch[pos][1];
			}
			else pos=ch[pos][0];
		}
		return ans;
	}
	T Suf(int id,T v){
		int pos=id,ans=Inf;
		while(pos){
			if(v<val[pos]){
				ans=ans<val[pos]?ans:val[pos];
				pos=ch[pos][0];
			}
			else pos=ch[pos][1];
		}
		return ans;
	}
	void insert(int root_id,T v){Insert(root[root_id],v);}
	void erase(int root_id,T v){Erase(root[root_id],v);}
	int rank(int root_id,T v){return Rank(root[root_id],v);}//如果需要，记得+1 
	T kth(int root_id,int rk){return Kth(root[root_id],rk);}
	T pre(int root_id,T v){return Pre(root[root_id],v);}
	T suf(int root_id,T v){return Suf(root[root_id],v);}
};
struct Tree{
	Treap<int> S;
	int n,a[MAXN],lef[MAXN],rig[MAXN];
	void build(int k,int L,int R){
		lef[k]=L,rig[k]=R;
		_rep(i,L,R)
		S.insert(k,a[i]);
		if(L==R)
		return;
		int M=L+R>>1;
		build(k<<1,L,M);
		build(k<<1|1,M+1,R);
	}
	void build(int n){build(1,1,n);}
	int Rank(int k,int L,int R,int v){
		if(L<=lef[k]&&rig[k]<=R)
		return S.rank(k,v);
		int mid=lef[k]+rig[k]>>1;
		if(mid>=R)
		return Rank(k<<1,L,R,v);
		else if(mid<L)
		return Rank(k<<1|1,L,R,v);
		else
		return Rank(k<<1,L,R,v)+Rank(k<<1|1,L,R,v);
	}
	int rank(int L,int R,int v){return Rank(1,L,R,v)+1;}
	int kth(int L,int R,int rk){
		int lef=0,rig=1e8,mid,trk,ans=0;
		while(lef<=rig){
			mid=lef+rig>>1;
			trk=rank(L,R,mid);
			if(trk<=rk){
				ans=mid;
				lef=mid+1;
			}
			else if(trk>rk)
			rig=mid-1;
		}
		return ans;
	}
	void update(int k,int pos,int v){
		S.erase(k,a[pos]);
		S.insert(k,v);
		if(lef[k]==rig[k]){
			a[pos]=v;
			return;
		}
		int mid=lef[k]+rig[k]>>1;
		if(pos<=mid)
		update(k<<1,pos,v);
		else
		update(k<<1|1,pos,v);
	}
	void update(int pos,int v){update(1,pos,v);}
	int Pre(int k,int L,int R,int v){
		if(L<=lef[k]&&rig[k]<=R)
		return S.pre(k,v);
		int mid=lef[k]+rig[k]>>1;
		if(mid>=R)
		return Pre(k<<1,L,R,v);
		else if(mid<L)
		return Pre(k<<1|1,L,R,v);
		else
		return max(Pre(k<<1,L,R,v),Pre(k<<1|1,L,R,v));
	}
	int pre(int L,int R,int v){return Pre(1,L,R,v);}
	int Suf(int k,int L,int R,int v){
		if(L<=lef[k]&&rig[k]<=R)
		return S.suf(k,v);
		int mid=lef[k]+rig[k]>>1;
		if(mid>=R)
		return Suf(k<<1,L,R,v);
		else if(mid<L)
		return Suf(k<<1|1,L,R,v);
		else
		return min(Suf(k<<1,L,R,v),Suf(k<<1|1,L,R,v));
	}
	int suf(int L,int R,int v){return Suf(1,L,R,v);}
}tree;
int main()
{
	int n=read_int(),m=read_int(),opt,l,r,pos,k,ans;
	_rep(i,1,n)
	tree.a[i]=read_int();
	tree.build(n);
	while(m--){
		opt=read_int();
		if(opt==3){
			pos=read_int(),k=read_int();
			tree.update(pos,k);
		}
		else{
			l=read_int(),r=read_int(),k=read_int();
			switch(opt){
				case 1:
					ans=tree.rank(l,r,k);
					break;
				case 2:
					ans=tree.kth(l,r,k);
					break;
				case 4:
					ans=tree.pre(l,r,k);
					break;
				case 5:
					ans=tree.suf(l,r,k);
					break;
			}
			enter(ans);
		}
	}
    return 0;
}