#include<bits/stdc++.h>
#define int long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define debug puts("-----------")
#define endl puts("")
#define re register
#define in inline
using namespace std;
const int N=2e5+7;

char *p1,*p2,buf[N];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
in int read(){
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57){
        if(ch=='-') f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57) x=x*10+ch-48,ch=nc();
   	return x*f;
}

struct node{
	int l,r,sum;
};
node tree[N<<4];
int root[N];
int n,m,Root;
int dele[N],Del;
int tot;
in int newNode(){
	if(Del) return dele[Del--];
	else return ++tot;
}
in void push_up(int p){
	tree[p].sum=tree[tree[p].l].sum+tree[tree[p].r].sum;
}
in void update(int &p,int pl,int pr,int i,int v){
	if(!p) p=newNode();
	if(pl==pr){
		tree[p].sum+=v;
		return ;
	}
	int mid=pl+pr>>1;
	if(i<=mid) update(tree[p].l,pl,mid,i,v);
	else update(tree[p].r,mid+1,pr,i,v);
	push_up(p);
}
in void Delete(int p){
	tree[p].sum=0;
	tree[p].l=tree[p].r=0;
	dele[++Del]=p;
}
in void merge(int &a,int b,int pl,int pr){
	if(!a||!b){
		a+=b;
		return ;
	}
	if(pl==pr){
		tree[a].sum+=tree[b].sum;
		Delete(b);
		return ;
	}
	int mid=pl+pr>>1;
	merge(tree[a].l,tree[b].l,pl,mid);
	merge(tree[a].r,tree[b].r,mid+1,pr);
	push_up(a);
	Delete(b);
}
in void split(int a,int &b,int p){
	if(!a) return ;
	b=newNode();
	int v=tree[tree[a].l].sum;
	if(v<p) split(tree[a].r,tree[b].r,p-v);
	else{
		swap(tree[a].r,tree[b].r);
	}
	if(v>p){
		split(tree[a].l,tree[b].l,p);
		tree[b].sum=tree[a].sum-p;
		tree[a].sum=p;
	}
}
in int querySum(int p,int pl,int pr,int L,int R){
	if(pl==L&&pr==R){
		return tree[p].sum;
	}
	int mid=pl+pr>>1;
	if(R<=mid) return querySum(tree[p].l,pl,mid,L,R);
	else if(L>mid) return querySum(tree[p].r,mid+1,pr,L,R);
	else{
		return querySum(tree[p].l,pl,mid,L,mid)+querySum(tree[p].r,mid+1,pr,mid+1,R);
	}
}
in int queryVal(int p,int pl,int pr,int rank){
	if(pl==pr) return pl;
	int mid=pl+pr>>1;
	if(tree[tree[p].l].sum<rank) return queryVal(tree[p].r,mid+1,pr,rank-tree[tree[p].l].sum);
	else{
		return queryVal(tree[p].l,pl,mid,rank);
	}
}
signed main(){
	n=read(),m=read();
	Root=1;
	for(re int i=1;i<=n;i++){
		int v=read();
		update(root[1],1,n,i,v);
	}
	for(re int i=1;i<=m;i++){
		int op=read();
		if(op==0){
			int now=0;
			int p=read(),x=read(),y=read();
			int sum1=querySum(root[p],1,n,1,y);
			int sum2=querySum(root[p],1,n,x,y);
			split(root[p],root[++Root],sum1-sum2);
			split(root[Root],now,sum2);
			merge(root[p],now,1,n);
		}
		else if(op==1){
			int p=read(),t=read();
			merge(root[p],root[t],1,n);
		}
		else if(op==2){
			int p=read(),x=read(),q=read();
			update(root[p],1,n,q,x);
		}
		else if(op==3){
			int p=read(),x=read(),y=read();
			printf("%lld\n",querySum(root[p],1,n,x,y));
		}
		else{
			int p=read(),rank=read();
			if(rank<0||tree[root[p]].sum<rank) puts("-1");
			else printf("%lld\n",queryVal(root[p],1,n,rank));
		}
	}
	return 0;
}