#include<iostream>
#include<cstring>
using namespace std;
const int INF=0x7fffffff;
const int LIM=1e8+2;
const int N=5e4+10;
int a[N];
int n,m;
int lowbit(int x){
	return x&(-x);
}
struct node{
	int lson,rson,sum;
}tree[800*N];
int root[N];
int tt;
void push_up(int pos){
	tree[pos].sum=tree[tree[pos].lson].sum+tree[tree[pos].rson].sum;
}
void upd(int &pos,int dot,int x,int l,int r){
	if(!pos) pos=++tt;
	if(l==r){
		tree[pos].sum+=x;
		return;
	}
	int mid=(l+r)/2;
	if(dot<=mid) upd(tree[pos].lson,dot,x,l,mid);
	else upd(tree[pos].rson,dot,x,mid+1,r);
	push_up(pos);
}
int cntl,cntr;
int lroot[N],rroot[N],trl[40][N],trr[40][N];
int xld;
int ask1(int lft,int rgt,int l,int r){
	if(rgt<l||r<lft) return 0;
	if(lft<=l&&r<=rgt){
		int tmp=0;
		for(int i=1;i<=cntr;i++){
			tmp+=tree[rroot[i]].sum;
		}
		for(int i=1;i<=cntl;i++){
			tmp-=tree[lroot[i]].sum;
		}
		return tmp;
	}
	int now=++xld;
	int mid=(l+r)/2;
	int tmp=0;
	for(int i=1;i<=cntl;i++){
		trl[now][i]=lroot[i];
	}
	for(int i=1;i<=cntr;i++){
		trr[now][i]=rroot[i];
	}
	for(int i=1;i<=cntl;i++){
		lroot[i]=tree[trl[now][i]].lson;
	}
	for(int i=1;i<=cntr;i++){
		rroot[i]=tree[trr[now][i]].lson;
	}
	tmp+=ask1(lft,rgt,l,mid);
	for(int i=1;i<=cntl;i++){
		lroot[i]=tree[trl[now][i]].rson;
	}
	for(int i=1;i<=cntr;i++){
		rroot[i]=tree[trr[now][i]].rson;
	}
	tmp+=ask1(lft,rgt,mid+1,r);
	for(int i=1;i<=cntl;i++){
		lroot[i]=trl[now][i];
	}
	for(int i=1;i<=cntr;i++){
		rroot[i]=trr[now][i];
	}
	return tmp;		
}
int ask2(int rk,int l,int r){
	//cout<<l<<" "<<r<<" "<<rk<<endl;
	if(l==r){
		return l;
	}
	int tmp=0,checker=0;
	for(int i=1;i<=cntr;i++){
		tmp+=tree[tree[rroot[i]].lson].sum;
		checker+=tree[rroot[i]].sum;
	}
	for(int i=1;i<=cntl;i++){
		tmp-=tree[tree[lroot[i]].lson].sum;
		checker-=tree[lroot[i]].sum;
	}
	if(!checker) return -1;
	int mid=(l+r)/2;
	if(rk>tmp){
		for(int i=1;i<=cntr;i++){
			rroot[i]=tree[rroot[i]].rson;
		}
		for(int i=1;i<=cntl;i++){
			lroot[i]=tree[lroot[i]].rson;
		}
		return ask2(rk-tmp,mid+1,r);
	}else{
		for(int i=1;i<=cntr;i++){
			rroot[i]=tree[rroot[i]].lson;
		}
		for(int i=1;i<=cntl;i++){
			lroot[i]=tree[lroot[i]].lson;
		}
		return ask2(rk,l,mid);		
	}
}
int yhqr1(int lft,int rgt,int k){//查排名 
	if(k==0) return 1;
	lft--;
	cntl=cntr=0;
	while(lft>0){
		lroot[++cntl]=root[lft];
		lft-=lowbit(lft);
	}
	while(rgt>0){
		rroot[++cntr]=root[rgt];
		rgt-=lowbit(rgt);
	}
	xld=0;
	return ask1(0,k-1,0,LIM)+1;
}
int yhqr2(int lft,int rgt,int k){//查数 
	lft--;
	cntl=cntr=0;
	while(lft>0){
		lroot[++cntl]=root[lft];
		lft-=lowbit(lft);
	}
	while(rgt>0){
		rroot[++cntr]=root[rgt];
		rgt-=lowbit(rgt);
	}
	return ask2(k,0,LIM);
}
int lqr1[N],lqr2[N];
int yhqr3(int lft,int rgt,int k){
	if(k==0) return -INF;
	lft--;
	cntl=cntr=0;
	while(lft>0){
		lroot[++cntl]=root[lft];
		lft-=lowbit(lft);
	}
	while(rgt>0){
		rroot[++cntr]=root[rgt];
		rgt-=lowbit(rgt);
	}
	for(int i=1;i<=cntl;i++){
		lqr1[i]=lroot[i];
	}
	for(int i=1;i<=cntr;i++){
		lqr2[i]=rroot[i];
	}
	xld=0;
	int num=ask1(0,k-1,0,LIM);
	for(int i=1;i<=cntl;i++){
		lroot[i]=lqr1[i];
	}
	for(int i=1;i<=cntr;i++){
		rroot[i]=lqr2[i];
	}
	int sbzyh=ask2(num,0,LIM);
	if(sbzyh==-1) return -INF;
	else return sbzyh;
}
int yhqr4(int lft,int rgt,int k){
	if(k==int(1e8)) return INF;
	lft--;
	cntl=cntr=0;
	while(lft>0){
		lroot[++cntl]=root[lft];
		lft-=lowbit(lft);
	}
	while(rgt>0){
		rroot[++cntr]=root[rgt];
		rgt-=lowbit(rgt);
	}
	for(int i=1;i<=cntl;i++){
		lqr1[i]=lroot[i];
	}
	for(int i=1;i<=cntr;i++){
		lqr2[i]=rroot[i];
	}
	xld=0;
	int num=ask1(0,k,0,LIM);
	//cout<<"AC\n";
	for(int i=1;i<=cntl;i++){
		//cout<<lroot[i]<<" ";
		lroot[i]=lqr1[i];
	}
	//cout<<endl;
	for(int i=1;i<=cntr;i++){
		//cout<<rroot[i]<<" ";
		rroot[i]=lqr2[i];
	}
	//cout<<endl;
	int sbzyh=ask2(num+1,0,LIM);
	if(sbzyh==-1) return INF;
	else return sbzyh;
}
void qryh(int dot,int x,int y,bool mode){
	a[dot]=y;
	while(dot<=n){
		if(mode) upd(root[dot],x,-1,0,LIM);
		upd(root[dot],y,1,0,LIM);
		dot+=lowbit(dot);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int xx;
		cin>>xx;
		qryh(i,0,xx,false);
	}
	while(m--){
		int op,ll,rr,kk;
		cin>>op>>ll>>rr;
		if(op==1){
			cin>>kk;
			cout<<yhqr1(ll,rr,kk)<<'\n'; 
		}else if(op==2){
			cin>>kk;
			cout<<yhqr2(ll,rr,kk)<<'\n';
		}else if(op==3){
			qryh(ll,a[ll],rr,true);
		}else if(op==4){
			cout<<yhqr3(ll,rr,kk)<<'\n';	
		}else if(op==5){
			cout<<yhqr4(ll,rr,kk)<<'\n';
		}
	}
	return 0;
}