#include <bits/stdc++.h>

#include "candies.h"

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(24);
const ll inf = 1.5e9;

int n;
vector<ll> c;
int q;
vector<int> ql, qr;
vector<ll> qv;
vector<int> rs;

void solve_l0_rn() {
    rs.resize(n);
    vector<pair<ll, ll>> stck;
    stck.push_back(make_pair(0, inf));
    stck.reserve(q);
    for (int i = 0; i < q; i += 1) {
        ll v = qv[i];
        ll x = abs(v);
        if (v == 0) {
            continue;
        }
        if (v >= 0) {
            while (x > 0) {
                auto f = stck.back();
                stck.pop_back();
                if (f.second > x) {
                    f.second -= x;
                    f.first += x;
                    x = 0;
                    stck.push_back(f);
                    break;
                } else if (stck.empty()) {
                    f.first += f.second;
                    f.second = 0;
                    x = 0;
                    stck.push_back(f);
                    break;
                } else {
                    x -= f.second;
                    stck.back().first += f.first + f.second;
                }
            }
        } else {
            ll sm = 0;
            while (x > 0) {
                auto f = stck.back();
                stck.pop_back();
                if (f.first > x) {
                    f.first -= x;
                    stck.push_back(f);
                    sm += x;
                    x = 0;
                    break;
                } else if (stck.empty()) {
                    f.second += f.first;
                    f.first = 0;
                    x = 0;
                    stck.push_back(f);
                    break;
                } else {
                    x -= f.first;
                    sm += f.first + f.second;
                }
            }
            if (sm > 0) {
                stck.push_back(make_pair(0, sm));
            }
        }
    }
    vector<pair<ll, ll>> bbr;
    bbr.reserve((int)stck.size() * 2 + 1);
    ll sm = 0;
    ll pos = 0;
    bbr.push_back(make_pair(pos, sm));
    while (!stck.empty()) {
        auto f = stck.back();
        stck.pop_back();
        pos += f.first;
        sm += f.first;
        if (bbr.back().first != pos) {
            bbr.push_back(make_pair(pos, sm));
        }
        pos += f.second;
        if (bbr.back().first != pos) {
            bbr.push_back(make_pair(pos, sm));
        }
    }
    for (int i = 0; i < n; i += 1) {
        ll ps = c[i];
        int j = upper_bound(all(bbr), make_pair(ps, inf * 5)) - bbr.begin();
        auto [ps0, sm0] = bbr[j - 1];
        auto [ps1, sm1] = bbr[j];
        ll val = ((ps1 - ps) * sm0 + (ps - ps0) * sm1) / (ps1 - ps0);
        rs[i] = val;
    }
}

vector<int> distribute_candies(vector<int> _c, vector<int> _l, vector<int> _r, vector<int> _v) {
    n = _c.size();
    q = _l.size();
    c.resize(n);
    for (int i = 0; i < n; i += 1) {
        c[i] = _c[i];
    }
    ql.resize(q);
    qr.resize(q);
    qv.resize(q);
    for (int i = 0; i < q; i += 1) {
        ql[i] = _l[i];
        qr[i] = _r[i];
        qv[i] = _v[i];
    }
    solve_l0_rn();
    return rs;
}