int t[4 * N], upd[4 * N];


void push(int v){
    upd[v * 2] += upd[v];
    upd[v * 2 + 1] += upd[v];
    t[v] += upd[v];
    upd[v] = 0;
}


void add(int v, int l, int r, int L, int R, int val){
    push(v);
    if (l >= r || L >= R)
        return;
    if (l == L && r == R){
        upd[v] += val;
        push(v);
        return;
    }
    int m = (l + r) / 2;
    add(v * 2, l, m, L, min(R, m), val);
    add(v * 2 + 1, m, r, max(L, m), R, val);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}


int getRg(int v, int l, int r, int val){
    push(v);
    if (l == r - 1)
        return (t[v] >= val ? l : -1);
    int m = (l + r) / 2;
    if (t[v * 2 + 1] >= val)
        return getRg(v * 2 + 1, m, r, val);
    else
        return getRg(v * 2, l, m, val);
}