$RT$

• 禁止无意义回复

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

const int N=2e5+5;

int n,m,x,Rt[N],buc[N];
int sum,cnt,gs,ch[N<<5][2],ans;
long long val[N<<5];

inline int New()
{
	return (sum)?buc[sum--]:++cnt;
}

inline void del(int &x)
{
	buc[++sum]=x;
	val[x]=ch[x][0]=ch[x][1]=0;
}

inline void update(int &x,int l,int r,int pos,int v)
{
	if(!x) x=New();
	val[x]+=v;
	if(l==r) return;
	int mid=(l+r)/2;
	if(pos<=mid) update(ch[x][0],l,mid,pos,v);
	else update(ch[x][1],mid+1,r,pos,v);
}

long long ask(int x,int l,int r,int ll,int rr)
{
	if(ll>r||rr<l) return 0;
	if(ll<=l&&r<=rr) return val[x];
	int mid=(l+r)/2;
	int ans=0;
	if(ll<=mid) ans+=ask(ch[x][0],l,mid,ll,rr);
	if(rr>mid) ans+=ask(ch[x][1],mid+1,r,ll,rr);
	return ans;
}

inline int merge(int x,int y)
{
	if(!x||!y) return x+y;
	val[x]+=val[y];
	ch[x][0]=merge(ch[x][0],ch[y][0]);
	ch[x][1]=merge(ch[x][1],ch[y][1]);
	del(y);
	return x;
}

inline void split(int x,int &y,int v)
{
	y=New();
	int tmp=val[ch[x][0]];
	if(v>tmp) 
		split(ch[x][1],ch[y][1],v-tmp);
	else swap(ch[x][1],ch[y][1]);
	if(v<tmp) split(ch[x][0],ch[y][0],v);
	val[y]=val[x]-v;
	val[x]=v;
}

inline int kth(int x,int l,int r,int pos)
{
	if(l==r) return l;
	int mid=(l+r)/2;
	if(val[ch[x][0]]>=pos) return kth(ch[x][0],l,mid,pos);
	else return kth(ch[x][1],mid+1,r,pos-val[ch[x][0]]);
}

signed main()
{
	n=read();
	m=read();
	for ( int i=1;i<=n;i++ ) update(Rt[1],1,n,i,read());
	gs=1;
	for (;m--;)
	{
		int op,x,y,z;
		op=read();
		if(!op)
		{
			x=read(),y=read(),z=read();
			long long gs1=ask(Rt[x],1,n,1,z);//[1,z]
			long long gs2=ask(Rt[x],1,n,y,z);//[y,z]
			int tmp=0;
			split(Rt[x],Rt[++gs],gs1-gs2);
			//Rt[++gs]:[y,n],Rt[x]:[1,y) 
			split(Rt[gs],tmp,gs2);
			//tmp:(z,n],Rt[gs]:[y,z] 
			Rt[x]=merge(Rt[x],tmp);
			//Rt[x]=[1,y)+(z,n] 
		}
		if(op==1)
		{
			x=read(),y=read();
			Rt[x]=merge(Rt[x],Rt[y]);
		}
		if(op==2)
		{
			x=read(),y=read(),z=read();
			update(Rt[x],1,n,z,y);
		}
		if(op==3)
		{
			x=read(),y=read(),z=read();
			printf("%lld\n",ask(Rt[x],1,n,y,z));
		}
		if(op==4)
		{
			x=read(),y=read();
			if(val[Rt[x]]<y)puts("-1");
			else printf("%d\n",kth(Rt[x],1,n,y));
		}
	}
	return 0;
}