#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
struct node {
ll l, h, s;
node(ll v = 0) : l(min(0ll, v)), h(max(0ll, v)), s(v) {}
node(ll l, ll h, ll s) : l(l), h(h), s(s) {}
node operator+ (const node& b) const {
return { min(l, s + b.l), max(h, s + b.h), s + b.s };
}
};
struct state {
ll l, r, q;
operator bool() const {
return l <= r;
}
ll operator() (ll x) const {
if (x < q) {
return l;
} else {
return min(x - q + l, r);
}
}
state(node n, ll c) {
l = n.s - n.l;
r = c + n.s - n.h;
q = min(c, -n.l);
}
};
struct segtree {
static constexpr int maxn = 262144;
vector<node> a;
segtree() : a(2*maxn) {}
void update(int p, int v) {
p += maxn;
a[p] = node(v);
for (int x=p>>1; x; x>>=1) {
a[x] = a[2*x] + a[2*x+1];
}
}
ll solve(ll y, ll c, int x=1, int w=maxn) {
if (w == 1) {
return min(c, max(0ll, y + a[x].s));
}
auto st = state(a[x], c);
if (st) {
return st(y);
}
auto st_r = state(a[2*x+1], c);
if (st_r) {
return st_r(solve(y, c, 2*x, w >> 1));
} else {
return solve(0, c, 2*x+1, w >> 1);
}
}
};
vi distribute_candies(vi c, vi l, vi r, vi v) {
int n = c.size();
int q = l.size();
vector<vi> e(n+1), f(n+1);
for (int i=0; i<q; i++) {
e[l[i]].push_back(i);
f[r[i]+1].push_back(i);
}
segtree st;
vi sol(n);
for (int i=0; i<n; i++) {
for (int j : e[i]) {
st.update(j, v[j]);
}
for (int j : f[i]) {
st.update(j, 0);
}
sol[i] = st.solve(0, c[i]);
}
return sol;
}
