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;
}