#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << endl;
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue
template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;
#include "candies.h"
vi distribute_candies(vi c, vi l, vi r, vi v) {
//cout << "SUM: " << accumulate(all(v), 0LL) << endl;
int n = c.size(), q = l.size();
vl pf(q+1);
V<pair<ll, int>> mx(q+1), mn(q+1);
f0r(i, q) {
pf[i+1] = pf[i] + v[i];
mx[i+1] = mn[i+1] = {pf[i+1], i+1};
}
for (int i = q-1; i >= 0; --i) {
mn[i] = min(mn[i], mn[i+1]);
mx[i] = max(mx[i], mx[i+1]);
}
//f0r(i, q+1) {
// cout << i << ' ' << mn[i].F << ' ' << mx[i].F << endl;
//}
//ctl(pf);
//cout << mn[0].F << ' ' << mx[1].F << ' ' << pf[q] << endl;
vi s(n);
f0r(i, n) {
int l = 0, r = q, x = -1;
auto p = mx[0];
mx[0] = max(mx[0], {c[i], 0});
while (l <= r) {
int m = (l+r)/2;
if (mx[m].F - mn[m].F >= c[i]) {
x = m;
l = m+1;
} else r = m-1;
}
mx[0] = p;
//cout << "CHEK: " << i << ' ' << x << ' ' << mn[x].S << endl;
if (x == -1) {
s[i] = pf[q];
//if (i == 7) cout << "YO" << endl;
} else {
if (mn[x].S == x) {
//if (i == 7) cout << "YO2" << endl;
int y = mx[x].S;
s[i] = pf[q] - pf[y] + c[i];
} else {
int y = mn[x].S;
s[i] = pf[q] - pf[y];
}
}
}
//cout << s[7] << endl;
return s;
}
