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