#include <iostream>
using namespace std;
typedef long long LL;
const int N = 200005, inf = 2e5;
struct Tree{
	int ls, rs;
	LL v;
}tr[N << 5];
int sta[N << 5], top, idx = 1;
int rt[N];
inline int newnode()
{
	return top ? sta[top --] : ++ idx;
}
inline void remove(int u)
{
	tr[u] = {0, 0, 0};
	sta[++ top] = u;
}
void update(int& u,int l,int r,int p,int x)
{
	if (!u)
		u = newnode();
	tr[u].v += x;
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	if (p <= mid)
		update(tr[u].ls, l, mid, p, x);
	else
		update(tr[u].rs, mid + 1, r, p, x);
}
LL query(int u,int l,int r,int L,int R)
{
	if (!u || l>R || L>r)
		return 0;
	if (L <= l && r <= R)
		return tr[u].v;
	int mid = (l + r) >> 1;
	LL res = 0;
	if (L <= mid)
		res = query(tr[u].ls, l, mid, L, R);
	if (mid < R)
		res += query(tr[u].rs, mid + 1, r, L, R);
	return res;
}
int get_k(int u,int l,int r,LL k)
{
	if (tr[u].v < k)
		return -1;
	if (l == r)
		return l;
	int mid = (l + r) >> 1;
	if (tr[tr[u].ls].v >= k)
		return get_k(tr[u].ls, l, mid, k);
	return get_k(tr[u].rs, mid + 1, r, k - tr[tr[u].ls].v);
}
int merge(int x,int y)
{
	if (!x || !y)
		return x | y;
	tr[x].v += tr[y].v;
	tr[x].ls = merge(tr[x].ls, tr[y].ls);
	tr[x].rs = merge(tr[x].rs, tr[y].rs);
	remove(y);
	return x;
}
void split(int x,int& y,LL k)
{
	if (!x)
		return;
	y = newnode();
	LL v = tr[tr[x].ls].v;
	if (k > v)
		split(tr[x].rs, tr[y].rs, k - v);
	else
		swap(tr[x].rs, tr[y].rs);
	if (k < v)
		split(tr[x].ls, tr[y].ls, k);
	tr[y].v = tr[x].v - k;
	tr[x].v = k;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, m;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		update(rt[1], 1, inf, i, x);
	}
	int tot = 1;
	while (m--)
	{
		int op, p, x;
		cin>>op>>p>>x;
		if (op == 0)
		{
			LL y;
			cin>>y;
			tot ++;
			LL s1 = query(rt[p], 1, inf, 1, y), s2 = query(rt[p], 1, inf, x, y);
			split(rt[p], rt[tot], s1 - s2);
			split(rt[tot], op, s2);
			rt[x] = merge(rt[x], op);
		}
		else if (op == 1)
			rt[p] = merge(rt[p], rt[x]);
		else if (op == 2)
		{
			LL q;
			cin>>q;
			update(rt[p], 1, inf, q, x);
		}
		else if (op == 3)
		{
			LL y;
			cin>>y;
			cout<<query(rt[p], 1, inf, x, y)<<'\n';
		}
		else
			cout<<get_k(rt[p], 1, inf, x)<<'\n';
		
	}
	return 0;
}