#include<bits/stdc++.h>
using namespace std;
int l[235],r[235],rr[235],a[50001],p[235][50001],ps[235][235],n,m,s;
vector<int> d[235],di[235];
vector<pair<int,int>> ds[235];
void init(){
	s=sqrt(n);
	int v[50001];
	for(int i=1;i<=n;i++) 
		v[i]=a[i];
	sort(v+1,v+n+1);
	for(int i=1;i<=s;i++){
		l[i]=v[n/s*(i-1)+1];
		r[i]=v[n/s*i];
		rr[i]=n/s*i;
	}
	r[s]=v[n];
	rr[s]=n;
	rr[0]=1;
	for(int i=1;i<=n;i++){
		int j=lower_bound(r+1,r+s+1,a[i])-r;
		d[j].push_back(a[i]);
		di[j].push_back(i);
		ds[j].push_back({a[i],i});
	}
	for(int i=1;i<=s;i++){
		sort(ds[i].begin(),ds[i].end());
		for(int j=0;j<d[i].size();j++)
			p[i][di[i][j]]=1;
		for(int j=1;j<=n;j++)
			p[i][j]=p[i][j-1]+p[i][j];
	}
}
int get_uda(int pos,int t){
	return p[pos][t]+ps[pos][(t+s-1)/s];
}
int get_bef(int x,int y,int k){
	int pos=1,bef=1;
	while(pos<=s&&r[pos]<=k){
		bef+=get_uda(pos,y)-get_uda(pos,x-1);
		pos++;
	}
	if(pos<=s&&l[pos]<=k){
		int j=0;
		while(j<d[pos].size()&&di[pos][j]<x) j++;
		while(j<d[pos].size()&&di[pos][j]<=y){
			if(d[pos][j]<=k) bef++;
			j++;
		}
	}
	return bef;
}
int get_kth(int x,int y,int k){
	int pos=1,bef=1,kth=0;
	while(pos<=s&&bef+get_uda(pos,y)-get_uda(pos,x-1)<k){
		bef+=get_uda(pos,y)-get_uda(pos,x-1);
		pos++;
	}
	if(pos<=s&&bef+get_uda(pos,y)-get_uda(pos,x-1)==k){
		for(int j=ds[pos].size()-1;j>=0;j--)
			if(ds[pos][j].second>=x&&ds[pos][j].second<=y)
				return ds[pos][j].first;
	}
	for(int j=0;j<ds[pos].size();j++){
		if(ds[pos][j].second>=x&&ds[pos][j].second<=y){
			bef++;
			if(bef==k){
				return ds[pos][j].first;
			}
		}
	}
}
void update(int pos,int k){
	int num=a[pos],p1=1,p2;
	while(p1<=s&&r[p1]<num) p1++;
	for(int j=0;j<d[p1].size();j++){
		if(d[p1][j]==num&&di[p1][j]==pos){
			d[p1].erase(d[p1].begin()+j);
			p2=di[p1][j];
			di[p1].erase(di[p1].begin()+j);
			break;
		}
	}
	int p2r=lower_bound(rr,rr+s+1,p2)-rr;
	if(rr[p2r]!=p2){
		for(int i=p2;i<=rr[p2r];i++) p[p1][i]--;
	}else p2r--;
	for(int i=p2r+1;i<=s;i++) ps[p1][i]--;
	for(int j=0;j<ds[p1].size();j++){
		if(ds[p1][j]==make_pair(num,pos)){
			ds[p1].erase(ds[p1].begin()+j);
			break;
		}
	}
	p1=1;p2=pos;
	while(p1<=s&&r[p1]<k) p1++;
	for(int j=0;j<d[p1].size();j++){
		if(di[p1][j]>pos){
			d[p1].insert(d[p1].begin()+j,k);
			di[p1].insert(di[p1].begin()+j,pos);
			break;
		}
	}
	p2r=lower_bound(rr,rr+s+1,p2)-rr;
	if(rr[p2r]!=p2){
		for(int i=p2;i<=rr[p2r];i++) p[p1][i]++;
	}else p2r--;
	for(int i=p2r+1;i<=s;i++) ps[p1][i]++;
	for(int j=0;j<ds[p1].size();j++){
		if(ds[p1][j].first>k){
			ds[p1].insert(ds[p1].begin()+j,{k,pos});
			break;
		}
	}
	a[pos]=k;
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	init();
	while(m--){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r,k;
			cin>>l>>r>>k;
			cout<<get_bef(l,r,k)<<endl;
		}else if(opt==2){
			int l,r,k;
			cin>>l>>r>>k;
			cout<<get_kth(l,r,k)<<endl;
		}else if(opt==3){
			int pos,k;
			cin>>pos>>k;
			update(pos,k);
		}else if(opt==4){
			int l,r,k;
			cin>>l>>r>>k;
			int tth=get_bef(l,r,k);
			if(tth==1) cout<<-2147483647<<endl;
			else{
				tth=get_bef(l,r,k-1);
				cout<<get_kth(l,r,tth)<<endl;
			}
		}else if(opt==5){
			int l,r,k;
			cin>>l>>r>>k;
			int tth=get_bef(l,r,k+1);
//			cout<<tth<<' '; 
			if(tth==r-l+1) cout<<2147483647<<endl;
			else cout<<get_kth(l,r,tth+1)<<endl;
		}
	}
	return 0;
}