#include<bits/stdc++.h>
#define int long long
#define maxn 200020
using namespace std;
int n,m;
int rt[maxn<<5],l[maxn<<5],r[maxn<<5],sum[maxn<<5],cnt,d;
stack<int> s;
inline void pushup(int x) {
	sum[x]=sum[l[x]]+sum[r[x]];
	return ;
}
inline void del(int p) {
	s.push(p);
	sum[p]=l[p]=r[p]=0;
	return ;
}
inline int input() {
	if(!s.empty()) {
		int t=s.top();
		s.pop();
		return t;
	}
	return ++cnt;
}
int query(int p,int x,int y,int L,int R) {
	if (!p) return 0;
	if (y<L&&R<x) return 0;
	if (L<=x&&y<=R) return sum[p];
	int mid=x+y>>1;
	return query(l[p],x,mid,L,R)+query(r[p],mid+1,y,L,R);
}
int query(int p,int x,int y,int k) {
	if(!p||k<=0) return -1;
	if(x==y) {
		if(sum[p]>=k) return x;
		return -1;
	}
	int mid=x+y>>1;
	if(l[p]&&sum[l[p]]>=k) return query(l[p],x,mid,k);
	else if(r[p]) return  query(r[p],mid+1,y,k-sum[l[p]]);
	return -1;
}
void modify(int &p,int L,int R,int x,int v) {
	if(!p) p=input();
	if(L==R) {
		sum[p]+=v;
		return ;
	}
	int mid=L+R>>1;
	if(x<=mid) modify(l[p],L,mid,x,v);
	else modify(r[p],mid+1,R,x,v);
	pushup(p);
	return ;
}
void split(int a,int &b,int k) {
	if(!a) return ;
	b=input();
	int cnt=sum[l[a]];
	if(k>cnt) {
		split(r[a],r[b],k-cnt);
	} else {
		swap(r[a],r[b]);
	}
	if(k<cnt) split(l[a],l[b],k);
	sum[b]=sum[a]-k;
	sum[a]=k;
	return ;
}
int merge(int a,int b,int L,int R) {
	if(!b) return a;
	if(!a) return b;
	if(L==R) {
		sum[a]+=sum[b];
		del(b);
		return a;
	}
	int mid=L+R>>1;
	l[a]=merge(l[a],l[b],L,mid);
	r[a]=merge(r[a],r[b],mid+1,R);
	pushup(a);
	del(b);
	return a;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	rt[d=1]=++cnt;
	for(int i=1;i<=n;i++){
		int num;
		cin>>num;
		modify(rt[1],1,n,i,num);
	}
	while(m--) {
		int op;
		cin>>op;
		if(op==0) {
			int p,x,y;
			cin>>p>>x>>y;
			int t1=query(rt[p],1,n,1,y);
			int t2=query(rt[p],1,n,x,y);
			split(rt[p],rt[++d],t1-t2);
			int tmp=0;
			split(rt[d],tmp,t2);
			rt[p]=merge(rt[p],tmp,1,n);
		}
		if(op==1) {
			int p,t;
			cin>>p>>t;
			rt[p]=merge(rt[p],rt[t],1,n);
		}
		if(op==2) {
			int p,x,q;
			cin>>p>>x>>q;
			modify(rt[p], 1, n, q, x);
		}
		if(op==3) {
			int p,x,y;
			cin>>p>>x>>y;
			cout<<query(rt[p],1,n,x,y)<<'\n';
		}
		if(op==4) {
			int p,k;
			cin>>p>>k;
			cout<<query(rt[p],1,n,k)<<'\n';
		}
	}
	return 0;
}