Rt
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define LL long long
#define int long long
int n,m,q;
struct node {
signed l,r;
signed lc,rc;
LL s;
}c[MAXN*30];
int p[MAXN];
int nn;
void rd() {
cin >> n >> q;
}
void up(int x) {
c[x].s = c[c[x].lc].s + c[c[x].rc].s;
}
int merge(int x,int y) {
if(!x || !y) return x+y;
c[x].s += c[y].s;
c[x].lc= merge(c[x].lc,c[y].lc);
c[x].rc = merge(c[x].rc,c[y].rc);
return x;
}
void split(int x,int y,int k) {
if(c[x].l == c[x].r) return;
int mid = (c[x].l + c[x].r)>>1;
if(mid == k) {
c[y].rc = c[x].rc;
c[x].rc = 0;
up(x); up(y);
return;
}
if(mid > k) {
c[y].rc = c[x].rc; c[x].rc = 0;
nn ++;
c[nn].l = c[c[x].lc].l;
c[nn].r = c[c[x].lc].r;
c[y].lc = nn;
split(c[x].lc,nn,k);
up(x); up(y);
}
if(mid < k) {
nn ++;
c[nn].l = c[c[x].rc].l;
c[nn].r = c[c[x].rc].r;
c[y].rc = nn;
split(c[x].rc,nn,k);
up(x); up(y);
}
}
void nnd() {
nn ++;
c[nn].l = 1;
c[nn].r = n;
c[nn].lc = c[nn].rc = 0;
}
void slp(int i,int x,int y) {
if(x == 1 && y == n) {
m ++;
p[m] = p[i];
nnd();
p[i] = nn;
return;
}
if(x == 1) {
nnd();
m ++;
int sr = nn;
split(p[i],nn,y);
p[m] = p[i];
p[i] = sr;
return;
}
if(y == n) {
nnd();
m ++;
p[m] = nn;
split(p[i],nn,x-1);
return;
}
nnd();
int ts = nn;
split(p[i],nn,y);
nnd();
int tr = nn;
split(p[i],nn,x-1);
// cout<<ts<<" "<<tr<<"\n";
m ++;
p[i] = merge(p[i],ts);
p[m] = tr;
}
void insert(int i,int x,int y) {
//5if(i <= 100)
//cout<<i<<" "<<c[i].l<<" "<<c[i].r<<"\n";
if(c[i].l == c[i].r) {
//cout<<c[i].s<<"?\n";
c[i].s += y;
return;
}
int mid = (c[i].l + c[i].r) >> 1;
if(x <= mid) {
if(c[i].lc == 0) {
nn ++;
c[i].lc = nn;
c[nn].l = c[i].l;
c[nn].r = mid;
}
insert(c[i].lc,x,y);
}
if(x > mid) {
if(c[i].rc == 0) {
nn ++;
c[i].rc = nn;
c[nn].l = mid+1;
c[nn].r = c[i].r;
}
insert(c[i].rc,x,y);
}
up(i);
}
int query(int i,int l,int r) {
if(l <= c[i].l && c[i].r <= r) return c[i].s;
if(l > c[i].r || r < c[i].l) return 0;
return query(c[i].lc,l,r) + query(c[i].rc,l,r);
}
int kth(int i,int k) {
if(c[i].s < k) return -1;
if(c[i].l == c[i].r) {
return c[i].l;
}
//if(k == 0) exit(-1);
if(k > c[c[i].lc].s) return kth(c[i].rc,k - c[c[i].lc].s);
else return kth(c[i].lc,k);
}
void QAQ(int i)
{
if(c[i].l == c[i].r) return;
if(i == 0) return;
QAQ(c[i].lc);
QAQ(c[i].rc);
up(i);
}
signed main()
{
rd();
nnd();
p[1] = nn;
m = 1;
for(int i = 1; i <= n; i ++) {
int x;
cin >> x;
insert(p[1],i,x);
}
int fucknn;
while(q --) {
fucknn ++;
int opt;
cin >> opt;
if(opt == 0) {
int t,x,y;
cin >> t >> x >> y;
//nnd();
//split(p[t],nn,y);
slp(t,x,y);
}
if(opt == 1) {
int x,y;
cin >> x >> y;
p[x] = merge(p[x],p[y]);
}
if(opt == 2) {
int t,x,y;
cin >> t >> x >> y;
insert(p[t],y,x);
}
if(opt == 3) {
int t,x,y;
cin >> t >> x >> y;
cout<<query(p[t],x,y)<<"\n";
}
if(opt == 4) {
int t,k;
cin >> t >> k;
cout<<kth(p[t],k)<<"\n";
}/*
for(int i = 1; i <= m; i ++)
cout<<i<<":"<<p[i]<<"\n";
cout<<"\n";
for(int i = 1; i <= nn; i ++) {
cout<<i<<":"<<c[i].l<<" "<<c[i].r<<" "<<c[i].lc<<" "<<c[i].rc<<" "<<c[i].s<<"\n";
}*/
c[0].l = c[0].r = c[0].s = c[0].lc = c[0].rc = 0;
}
return 0;
}