rt/kk

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 8e6 + 10;
int n, m, bin[N], ch[N][3], root[N];
int val[N], cnt, ck;
inline int read()
{
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        s = (s << 3) + (s << 1) + (ch ^ 48);
        ch = getchar();
    }
    return s * w;
}
int newnd(){return (cnt ? bin[cnt--] : ++ck);}
void del(int u)
{
    bin[++cnt] = u, ch[u][0] = ch[u][1] = val[u] = 0;
    return ;
}
void change(int &u, int l, int r, int x, int v)
{
    if(!u) u = newnd();
    val[u] += v;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(x <= mid) change(ch[u][0], l, mid, x, v);
    else change(ch[u][1], mid + 1, r, x, v);
    return ;
}
int query(int u, int l, int r, int L, int R)
{
    if(R < l || r < L) return 0;
    if(L <= l && r <= R) return val[u];
    int mid = (l + r) >> 1;
    return query(ch[u][0], l, mid, L, R) + query(ch[u][1], mid + 1, r, L, R);
}
int kth(int u, int l, int r, int k)
{
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(val[ch[u][0]] >= k) return kth(ch[u][0], l, mid, k);
    else return kth(ch[u][1], mid + 1, r, k - val[ch[u][0]]);
}
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;
}
void split(int x, int &y, int k)
{
    if(x == 0) return ;
    y = newnd();
    int v = val[ch[x][0]];
    if(k > v) split(ch[x][1], ch[y][1], k - v);
    else swap(ch[x][1], ch[y][1]);
    if(k < v) split(ch[x][0], ch[y][0], k);
    val[y] = val[x] - k;
    val[x] = k;
    return ;
}
int t1, t2;
int rtn;
signed main()
{
    n = read(), m = read();
    for(int i = 1; i <= n; i++) change(root[1], 1, n, i, read());
    for(int i = 1; i <= m; i++)
    {
        int opt = read();
        int x = read(), y = read(), z;
        if(opt == 0)
        {
            z = read();
            t1 = query(root[x], 1, n, 1, z);
            t2 = query(root[x], 1, n, y, z);
            int now = 0;
            split(root[x], root[++rtn], t1 - t2);
            split(root[rtn], now, t2);
            root[x] = merge(root[x], now);
        }
        if(opt == 1) root[x] = merge(root[x], root[y]);
        if(opt == 2) change(root[x], 1, n, read(), y);
        if(opt == 3) printf("%lld\n", query(root[x], 1, n, y, read()));
        if(opt == 4)
        {
            if(val[root[x]] < y)
            {
                printf("-1\n");
                continue;
            }
            printf("%lld\n", kth(root[x], 1, n, y));
        }
    }
    return 0;
}