#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) {}
};

pair<ll, int> umin(pair<ll, int> a, pair<ll, int> b) {
    return a.first != b.first ? min(a, b) : a.second > b.second ? a : b;
}

Info operator+(const Info &l, const Info &r) {
    Info res{};
    res.mx = max(l.mx, r.mx);
    res.mn = umin(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.assign(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;
    }

    int findSegmentBiggerThanC(int C, ll mx = -3e18, int x = 1, int lx = 0, int rx = sz) {
        if (lx + 1 == rx) {
            return lx;
        }
        push(x);
        int mid = lx + rx >> 1;
        if (t[x << 1 | 1].mxans >= C || mx - t[x << 1 | 1].mn.first >= C) {
            return findSegmentBiggerThanC(C, mx, x << 1 | 1, mid, rx);
        } else {
            return findSegmentBiggerThanC(C, max(mx, t[x << 1 | 1].mx.first), x << 1, lx, mid);
        }
    }

    int findSegmentSmallerThanC(int C, ll mn = 3e18, int x = 1, int lx = 0, int rx = sz) {
        if (lx + 1 == rx) {
            return lx;
        }
        push(x);
        int mid = lx + rx >> 1;
        if (t[x << 1 | 1].mnans <= C || mn - t[x << 1 | 1].mx.first <= C) {
            return findSegmentSmallerThanC(C, mn, x << 1 | 1, mid, rx);
        } else {
            return findSegmentSmallerThanC(C, min(mn, t[x << 1 | 1].mn.first), x << 1, lx, mid);
        }
    }

    Info rangeQuery(int l, int r, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return {};
        }
        if (l <= lx && rx <= r) {
            return t[x];
        }
        int mid = lx + rx >> 1;
        push(x);
        return rangeQuery(l, r, x << 1, lx, mid) + rangeQuery(l, r, x << 1 | 1, mid, rx);
    }
};

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 l1 = SegmentTree::t[1].mxans < c[i] ? q + 1 : SegmentTree::findSegmentBiggerThanC(c[i]);
        int r1 = SegmentTree::rangeQuery(l1 + 1, q + 1).mx.second;
        int l2 = SegmentTree::t[1].mnans > -c[i] ? q + 1 : SegmentTree::findSegmentSmallerThanC(-c[i]);
        int r2 = max(SegmentTree::rangeQuery(0, q + 1).mn.second, SegmentTree::rangeQuery(l2 + 1, q + 1).mn.second);
        if (r2 <= r1) {
            answers[i] = c[i] + sumAll - SegmentTree::query(r1);
        } else {
            answers[i] = sumAll - SegmentTree::query(r2);
        }
    }

    return answers;
}