#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
const int bits = 19;
const ll inf = 1e18;
ll mn[1<<20], mx[1<<20], lazy[1<<20];
const int MAXN = 6e5;
struct segtree {
ll lastval = 0, small = inf, big = -inf;
segtree() {}
void update(ll node, ll val) {
lastval += val;
node += (1<<bits);
lazy[node] += val;
while (node > 1) {
if (node%2==0) lazy[node+1] += val;
mn[node/2] = min(mn[node] + lazy[node], mn[node^1] + lazy[node^1]);
mx[node/2] = max(mx[node] + lazy[node], mx[node^1] + lazy[node^1]);
node /= 2;
}
}
ll solve(ll cap) {
ll node = 1;
small = inf;
big = -inf;
ll lz = 0;
while (node < (1<<bits)) {
lz += lazy[node];
node<<=1;
if (max(big, mx[node+1]+lazy[node+1]+lz) - min(small, mn[node+1]+lazy[node+1]+lz) > cap) node++;
else {
big = max(big, mx[node+1]+lazy[node+1]+lz);
small = min(small, mn[node+1]+lazy[node+1]+lz);
}
}
if (mn[node] + lazy[node] + lz < lastval) return cap - (big - lastval);
else return lastval - small;
}
};
vector<pll> toggle[MAXN];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
int q = l.size();
segtree seg;
for (int i = 0; i < q; i++) {
toggle[l[i]].push_back({i, v[i]});
toggle[r[i]+1].push_back({i, -v[i]});
}
vector<int> res(n);
for (int i = 0; i < n; i++) {
for (auto p : toggle[i]) seg.update(p.first+2, p.second);
if ((mx[1] - mn[1]) < c[i]) res[i] = (seg.lastval - (mn[1] + lazy[1]));
else res[i] = seg.solve(c[i]);
}
return res;
}
