#include "candies.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll infLL = 3e18;

struct Info {
    pair<ll, int> mx{-infLL, 0}, mn{infLL, 0};
    ll mxans = -infLL, mnans = infLL;
    Info() = default;
    Info(int i, ll x) : mx(x, i), mn(x, i) {}
};

Info operator+(const Info &l, const Info &r) {
    Info res{};
    res.mx = max(l.mx, r.mx);
    res.mn = min(l.mn, r.mn);
    res.mxans = max({l.mxans, r.mxans, r.mx.first - l.mn.first});
    res.mnans = min({l.mnans, r.mnans, r.mn.first - l.mx.first});
    return res;
}

namespace SegmentTree {
    vector<Info> t;
    vector<ll> tag;
    int sz = 1;

    void apply(int x, ll tg) {
        tag[x] += tg;
        t[x].mx.first += tg, t[x].mn.first += tg;
    }

    void push(int x) {
        if (tag[x]) {
            apply(x << 1, tag[x]);
            apply(x << 1 | 1, tag[x]);
            tag[x] = 0;
        }
    }

    void pull(int x) {
        t[x] = t[x << 1] + t[x << 1 | 1];
    }

    void init(int n) {
        sz = 1 << __lg(n) + !!(n & (n - 1));
        t.resize(sz << 1), tag.assign(sz << 1, 0);
        for (int i = 0; i < n; ++i) {
            t[i + sz] = Info(i, 0);
        }
        for (int i = sz - 1; i > 0; --i) {
            pull(i);
        }
    }

    void rangeAdd(int l, int r, int tg, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            return apply(x, tg);
        }
        int mid = lx + rx >> 1;
        push(x);
        rangeAdd(l, r, tg, x << 1, lx, mid);
        rangeAdd(l, r, tg, x << 1 | 1, mid, rx);
        pull(x);
    }

    ll query(int i, int x = 1, int lx = 0, int rx = sz) {
        while (lx + 1 < rx) {
            push(x);
            int mid = lx + rx >> 1;
            if (i < mid) {
                rx = mid;
                x = x << 1;
            } else {
                lx = mid;
                x = x << 1 | 1;
            }
        }
        return t[x].mx.first;
    }

    pair<ll, int> findMin(int l, int r, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return {infLL, -1};
        }
        if (l <= lx && rx <= r) {
            return t[x].mn;
        }
        int mid = lx + rx >> 1;
        push(x);
        return min(findMin(l, r, x << 1, lx, mid), findMin(l, r, x << 1 | 1, mid, rx));
    }

    pair<ll, int> findMax(int l, int r, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return {-infLL, -1};
        }
        if (l <= lx && rx <= r) {
            return t[x].mx;
        }
        int mid = lx + rx >> 1;
        push(x);
        return max(findMax(l, r, x << 1, lx, mid), findMax(l, r, x << 1 | 1, mid, rx));
    }

    pair<ll, int> queryMax(ll aim, int x, int lx, int rx) {
        assert(t[x].mx.first >= aim);
        if (lx + 1 == rx) {
            return t[x].mx;
        }
        int mid = lx + rx >> 1;
        push(x);
        if (t[x << 1 | 1].mx.first >= aim) {
            return queryMax(aim, x << 1 | 1, mid, rx);
        } else {
            return queryMax(aim, x << 1, lx, mid);
        }
    }

    pair<ll, int> queryMin(ll aim, int x, int lx, int rx) {
        assert(t[x].mn.first <= aim);
        if (lx + 1 == rx) {
            return t[x].mn;
        }
        int mid = lx + rx >> 1;
        push(x);
        if (t[x << 1 | 1].mn.first <= aim) {
            return queryMin(aim, x << 1 | 1, mid, rx);
        } else {
            return queryMin(aim, x << 1, lx, mid);
        }
    }

    pair<int, int> findSegmentBiggerThanC(int C, int x = 1, int lx = 0, int rx = sz) {
        pair<int, int> s{-1, -1};
        while (lx + 1 < rx && t[x].mxans >= C) {
            int mid = lx + rx >> 1;
            push(x);
            if (t[x << 1 | 1].mx.first - t[x << 1].mn.first >= C) {
                int R = queryMax(C + t[x << 1].mn.first, x << 1 | 1, mid, rx).second;
                s = max(s, {R, t[x << 1].mn.second});
            }
            if (t[x << 1 | 1].mxans >= C) {
                x = x << 1 | 1;
                lx = mid;
            } else {
                x = x << 1;
                rx = mid;
            }
        }
        return s;
    }

    pair<int, int> findSegmentSmallerThanC(int C, int x = 1, int lx = 0, int rx = sz) {
        assert(C <= 0);
        pair<int, int> s{-1, -1};
        while (lx + 1 < rx && t[x].mnans <= C) {
            int mid = lx + rx >> 1;
            push(x);
            if (t[x << 1 | 1].mn.first - t[x << 1].mx.first <= C) {
                int R = queryMin(C + t[x << 1].mx.first, x << 1 | 1, mid, rx).second;
                s = max(s, {R, t[x << 1].mx.second});
            }
            if (t[x << 1 | 1].mnans <= C) {
                x = x << 1 | 1;
                lx = mid;
            } else {
                x = x << 1;
                rx = mid;
            }
        }
        return s;
    }
};

void massert(bool f) {
    while (!f) {
        cout << "why" << endl;
    }
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> L,
                                    std::vector<int> R, std::vector<int> V) {
    int n = c.size(), q = size(L);

    std::vector<int> answers(n);
    vector<vector<int>> updates(n + 1);

    for (int i = 0; i < q; ++i) {
        updates[L[i]].push_back(i);
        updates[R[i] + 1].push_back(~i);
    }

    SegmentTree::init(q + 1);

    ll sumAll = 0;

    for (int i = 0; i < n; ++i) {
        for (int j : updates[i]) {
            if (j >= 0) {
                sumAll += V[j];
                SegmentTree::rangeAdd(j + 1, q + 1, V[j]);
            } else {
                j = ~j;
                sumAll -= V[j];
                SegmentTree::rangeAdd(j + 1, q + 1, -V[j]);
            }
        }
        int rbig = q + 1, lbig = -1;
        for (rbig -= 1; rbig >= 0; --rbig) {
            auto [x, y] = SegmentTree::findMin(0, rbig + 1);
            ll xx = SegmentTree::query(rbig);
            if (xx - x >= c[i]) {
                lbig = y;
                break;
            }
        }
        int rsmall = q + 1, lsmall = -1;
        for (rsmall -= 1; rsmall >= 0; --rsmall) {
            auto [x, y] = SegmentTree::findMax(0, rsmall + 1);
            ll xx = SegmentTree::query(rsmall);
            if (xx - x <= -c[i]) {
                lsmall = y;
                break;
            }
        }
//        auto [rbig, lbig] = SegmentTree::findSegmentBiggerThanC(c[i]);
//        auto [rsmall, lsmall] = SegmentTree::findSegmentSmallerThanC(-c[i]);
        if (rsmall != -1) {
            assert(SegmentTree::query(rsmall) - SegmentTree::query(lsmall) <= -c[i]);
            rsmall = SegmentTree::findMin(lsmall, rsmall + 1).second;
        }
        if (rbig != -1) {
            assert(SegmentTree::query(rbig) - SegmentTree::query(lbig) >= c[i]);
            rbig = SegmentTree::findMax(lbig, rbig + 1).second;
        }
        rsmall = max(rsmall, SegmentTree::findMin(0, q + 1).second);
        if (rsmall <= rbig) {
            ll got = c[i] + sumAll - SegmentTree::query(rbig);
            massert(got >= 0 && got <= c[i]);
            answers[i] = got;
        } else {
            ll got = sumAll - SegmentTree::query(rsmall);
            massert(got >= 0 && got <= c[i]);
            answers[i] = got;
        }
    }

    return answers;
}