#include "candies.h"

#include <bits/stdc++.h>

using namespace std;

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

struct Node {
    long long min, second_min, max, second_max;

    bool push_min, push_max;

    long long push_add;

    Node() {
        min = max = 0;
        second_min = inf;
        second_max = -inf;
        push_min = push_max = false;
        push_add = 0;
    }
};

constexpr int R = 1 << 18;

Node tree[R * 2];

void push(int node) {
    if (node >= R) {
        tree[node].push_min = tree[node].push_max = false;
        tree[node].push_add = 0;
        return;
    }
    if (tree[node].push_add != 0) {
        tree[node * 2].min += tree[node].push_add;
        if (tree[node * 2].second_min != inf) {
            tree[node * 2].second_min += tree[node].push_add;
        }
        tree[node * 2].max += tree[node].push_add;
        if (tree[node * 2].second_max != -inf) {
            tree[node * 2].second_max += tree[node].push_add;
        }
        tree[node * 2].push_add += tree[node].push_add;

        tree[node * 2 + 1].min += tree[node].push_add;
        if (tree[node * 2 + 1].second_min != inf) {
            tree[node * 2 + 1].second_min += tree[node].push_add;
        }
        tree[node * 2 + 1].max += tree[node].push_add;
        if (tree[node * 2 + 1].second_max != -inf) {
            tree[node * 2 + 1].second_max += tree[node].push_add;
        }
        tree[node * 2 + 1].push_add += tree[node].push_add;
    }
    tree[node].push_add = 0;
    if (tree[node].push_min) {
        if (tree[node].max < tree[node * 2].max) {
            tree[node * 2].max = tree[node].max;
            tree[node * 2].push_min = true;
        }
        if (tree[node].max < tree[node * 2 + 1].max) {
            tree[node * 2 + 1].max = tree[node].max;
            tree[node * 2 + 1].push_min = true;
        }
    }
    tree[node].push_min = false;
    if (tree[node].push_max) {
        if (tree[node].min > tree[node * 2].min) {
            tree[node * 2].min = tree[node].min;
            tree[node * 2].push_max = true;
        }
        if (tree[node].min > tree[node * 2 + 1].min) {
            tree[node * 2 + 1].min = tree[node].min;
            tree[node * 2 + 1].push_max = true;
        }
    }
    tree[node].push_max = false;
}

void relax(int node) {
    tree[node].min = min(tree[node * 2].min, tree[node * 2 + 1].min);
    if (tree[node].min != tree[node * 2].min) {
        tree[node].second_min = min(tree[node * 2].min, tree[node * 2 + 1].second_min);
    } else if (tree[node].min != tree[node * 2 + 1].min) {
        tree[node].second_min = min(tree[node * 2].second_min, tree[node * 2 + 1].min);
    } else {
        tree[node].second_min = min(tree[node * 2].second_min, tree[node * 2 + 1].second_min);
    }

    tree[node].max = max(tree[node * 2].max, tree[node * 2 + 1].max);
    if (tree[node].max != tree[node * 2].max) {
        tree[node].second_max = max(tree[node * 2].max, tree[node * 2 + 1].second_max);
    } else if (tree[node].max != tree[node * 2 + 1].max) {
        tree[node].second_max = max(tree[node * 2].second_max, tree[node * 2 + 1].max);
    } else {
        tree[node].second_max = max(tree[node * 2].second_max, tree[node * 2 + 1].second_max);
    }
}

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].min += val;
        if (tree[node].second_min != inf) {
            tree[node].second_min += val;
        }
        tree[node].max += val;
        if (tree[node].second_max != -inf) {
            tree[node].second_max += val;
        }
        tree[node].push_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) {
    push(node);
    if (mn <= tree[node].min) {
        return;
    }
    if (mn < tree[node].second_min) {
        tree[node].min = mn;
        tree[node].max = max(tree[node].max, mn);
        if (tree[node].second_max != -inf) {
            tree[node].second_max = max(tree[node].second_max, mn);
        }
        tree[node].push_max = true;
        return;
    }
    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) {
    push(node);
    if (tree[node].max <= mx) {
        return;
    }
    if (mx > tree[node].second_max) {
        tree[node].max = mx;
        tree[node].min = min(tree[node].min, mx);
        if (tree[node].second_min != inf) {
            tree[node].second_min = min(tree[node].second_min, mx);
        }
        tree[node].push_min = true;
        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].min;
    }
    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;
}