#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int pls[maxn*40],prs[maxn*40];
int sta[maxn*40],root[maxn],top,id;
long long cnt[maxn*40];
inline int newnode(){
	return top?sta[top--]:++id;
}
inline void delnode(int p){
	cnt[p]=0; sta[++top]=p; return;
}
inline void pushup(int p){
	cnt[p]=cnt[pls[p]]+cnt[prs[p]];
	return;
}
inline void update(int d,int &p,int pl,int pr,int k){
	if(!p) p=newnode();
	if(pl==pr){cnt[p]+=k;return;}
	int mid=(pl+pr)>>1;
	if(d<=mid) update(d,pls[p],pl,mid,k);
	else update(d,prs[p],mid+1,pr,k);
	return pushup(p);
}
inline void split(int l,int r,int &p,int &q,int pl,int pr){
	if(!p or l>pr or r<pl) return;
	if(l<=pl and pr<=r){q=p,p=0;return;}
	if(!q) q=newnode();
	int mid=(pl+pr)>>1;
	if(l<=mid) split(l,r,pls[p],pls[q],pl,mid);
	if(r>mid) split(l,r,prs[p],prs[q],mid+1,pr);
	return pushup(q);
}
inline void merge(int &p,int &q,int pl,int pr){
	if(!p) return;
	if(!q){q=p,p=0;return;}
	if(pl==pr){cnt[q]+=cnt[p];delnode(p);return;}
	int mid=(pl+pr)>>1;
	merge(pls[p],pls[q],pl,mid);
	merge(prs[p],prs[q],mid+1,pr);
	return pushup(q);
}
inline int querycnt(int l,int r,int p,int pl,int pr){
	if(!p) return 0;
	if(l<=pl and pr<=r) return cnt[p];
	int mid=(pl+pr)>>1,ans=0;
	if(l<=mid) ans+=querycnt(l,r,pls[p],pl,mid);
	if(r>mid) ans+=querycnt(l,r,prs[p],mid+1,pr);
	return ans;
}
inline int querykth(long long d,int p,int pl,int pr){
	if(pl==pr) return pl;
	int mid=(pl+pr)>>1;
	if(cnt[pls[p]]>=d) return querykth(d,pls[p],pl,mid);
	else return querykth(d-cnt[pls[p]],prs[p],mid+1,pr);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n,m;cin>>n>>m;
	int opt,id,v,now=1; long long u;
	for(int i=1;i<=n;i++){
		cin>>u; update(i,root[1],1,n,u);
	}
	for(int i=1;i<=m;i++){
		cin>>opt>>id>>u;
		if(opt^1 and opt^4) cin>>v;
		if(opt==0) split(u,v,root[id],root[++now],1,n);
		else if(opt==1) merge(root[id],root[u],1,n);
		else if(opt==2) update(v,root[id],1,n,u);
		else if(opt==3) cout<<querycnt(u,v,root[id],1,n)<<"\n";
		else if(cnt[root[id]]<u) cout<<"-1\n";
		else cout<<querykth(u,root[id],1,n)<<"\n";
	}
	return 0;
}