#include "candies.h"

#include <bits/stdc++.h>

using namespace std;

constexpr long long inf = (long long)1e18 + 7;

struct Node {
    long long mn, mn2, mx, mx2, mn_assign, mx_assign, add;

    Node() {
        mn = mn2 = mx = mx2 = 0;
        mn_assign = inf;
        mx_assign = 0;
        add = 0;
    }
};

constexpr int R = 1 << 18;

Node tree[R * 2];

void build() {
    for (int i = 0; i < R; ++i) {
        tree[i + R].mn2 = inf;
        tree[i + R].mx2 = -inf;
    }
}

void push(int node) {
    if (tree[node].add != 0) {
        tree[node * 2].mn += tree[node].add;
        tree[node * 2].mn2 += tree[node].add;
        tree[node * 2].mx += tree[node].add;
        tree[node * 2].mx2 += tree[node].add;
        tree[node * 2].mn_assign += tree[node].add;
        tree[node * 2].mx_assign += tree[node].add;
        tree[node * 2].add += tree[node].add;

        tree[node * 2 + 1].mn += tree[node].add;
        tree[node * 2 + 1].mn2 += tree[node].add;
        tree[node * 2 + 1].mx += tree[node].add;
        tree[node * 2 + 1].mx2 += tree[node].add;
        tree[node * 2 + 1].mn_assign += tree[node].add;
        tree[node * 2 + 1].mx_assign += tree[node].add;
        tree[node * 2 + 1].add += tree[node].add;
    }
    tree[node].add = 0;
    if (tree[node].mn_assign < inf) {
        if (tree[node * 2].mx > tree[node].mn_assign) {
            tree[node * 2].mx = tree[node].mn_assign;
        }
        tree[node * 2].mn_assign = min(tree[node * 2].mn_assign, tree[node].mn_assign);
        if (tree[node * 2 + 1].mx > tree[node].mn_assign) {
            tree[node * 2 + 1].mx = tree[node].mn_assign;
        }
        tree[node * 2 + 1].mn_assign = min(tree[node * 2 + 1].mn_assign, tree[node].mn_assign);
    }
    tree[node].mn_assign = inf;
    if (tree[node].mx_assign >= 0) {
        if (tree[node * 2].mn < tree[node].mx_assign) {
            tree[node * 2].mn = tree[node].mx_assign;
        }
        tree[node * 2].mx_assign = max(tree[node * 2].mx_assign, tree[node].mx_assign);
        if (tree[node * 2 + 1].mn < tree[node].mx_assign) {
            tree[node * 2 + 1].mn = tree[node].mx_assign;
        }
        tree[node * 2 + 1].mx_assign = max(tree[node * 2 + 1].mx_assign, tree[node].mx_assign);
    }
    tree[node].mx_assign = 0;
}

void relax(int node) {
    tree[node].mn = min(tree[node * 2].mn, tree[node * 2 + 1].mn);
    vector<long long> vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mn2, tree[node * 2 + 1].mn2, tree[node * 2].mx, tree[node * 2 + 1].mx, inf};
    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
    tree[node].mn2 = vals[1];
    tree[node].mx = max(tree[node * 2].mx, tree[node * 2 + 1].mx);
    vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mx2, tree[node * 2 + 1].mx2, tree[node * 2].mx, tree[node * 2 + 1].mx, -inf};
    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
    tree[node].mx2 = vals.rbegin()[1];
}

void add_val(int ql, int qr, int val, int node = 1, int nl = 0, int nr = R) {
    if (ql <= nl && nr <= qr) {
        tree[node].mn += val;
        tree[node].mn2 += val;
        tree[node].mx += val;
        tree[node].mx2 += val;
        tree[node].mn_assign += val;
        tree[node].mx_assign += val;
        tree[node].add += val;
        return;
    }
    if (qr <= nl || nr <= ql) {
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    add_val(ql, qr, val, node * 2, nl, nm);
    add_val(ql, qr, val, node * 2 + 1, nm, nr);
    relax(node);
}

void fix_mn(long long mn, int node = 1, int nl = 0, int nr = R) {
    if (mn <= tree[node].mn) {
        return;
    }
    if (nl == nr - 1) {
        tree[node].mn = tree[node].mx = mn;
        return;
    }
    if (mn < tree[node].mn2) {
        tree[node].mn = mn;
        tree[node].mx_assign = mn;
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    fix_mn(mn, node * 2, nl, nm);
    fix_mn(mn, node * 2 + 1, nm, nr);
    relax(node);
}

void fix_mx(long long mx, int node = 1, int nl = 0, int nr = R) {
    if (tree[node].mx <= mx) {
        return;
    }
    if (nl == nr - 1) {
        tree[node].mn = tree[node].mx = mx;
        return;
    }
    if (mx > tree[node].mx2) {
        tree[node].mx = mx;
        tree[node].mn_assign = mx;
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    fix_mx(mx, node * 2, nl, nm);
    fix_mx(mx, node * 2 + 1, nm, nr);
    relax(node);
}

long long get(int pos, int node = 1, int nl = 0, int nr = R) {
    if (nl == pos && nr == pos + 1) {
        return tree[node].mn;
    }
    if (nr <= pos || pos < nl) {
        return 0;
    }
    push(node);
    int nm = (nl + nr) / 2;
    long long ans = get(pos, node * 2, nl, nm) + get(pos, node * 2 + 1, nm, nr);
    relax(node);
    return ans;
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v) {
    int n = c.size();
    int q = v.size();
    vector<int> ans(n);
    for (int i = 0; i < q; ++i) {
        r[i]++;
        add_val(l[i], r[i], v[i]);
        fix_mn(0);
        fix_mx(c[0]);
    }
    for (int i = 0; i < n; ++i) {
        ans[i] = get(i);
    }
    return ans;
}