#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int > 
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define pb emplace_back
#define i128 __int128
using namespace std;
const int N = 1e6 + 7, mod = 1e9 + 7;

int n;
struct tag {
	ll inc;
	ll l, r;
	tag() {
		inc = 0;
		l = 0;
		r = mod;
	}
	ll calc(ll w) {
		return min(max(w + inc, l), r);
	}
};
tag operator + (tag l, tag r) {
	tag o;
	o.inc = l.inc + r.inc;
	o.l = r.calc(l.l);
	o.r = r.calc(l.r);
	return o;
}
vi ins[N], del[N];
int f[N];
ll sum[N], pmx[N], pmn[N];
void modify(int x, int L, int R, int p, int w) {
	if(L == R) {
		sum[x] = w;
		pmx[x] = max(w, 0);
		pmn[x] = min(w, 0);
		return;
	}
	int mid = (L + R) >> 1;
	p <= mid ? modify(x * 2, L, mid, p, w) : modify(x * 2 + 1, mid + 1, R, p, w);
	sum[x] = sum[x * 2] + sum[x * 2 + 1];
	pmx[x] = max(pmx[x * 2], sum[x] + pmx[x * 2 + 1]);
	pmn[x] = min(pmn[x * 2], sum[x] + pmn[x * 2 + 1]);
}
ll s, mx, mn, ans;
int cap;
void query(int x, int L, int R) {
	if(mx - mn >= cap) return;
	if(max(mx, s + pmx[x]) - min(mn, s + pmn[x]) < cap) {
		mx = max(mx, s + pmx[x]);
		mn = min(mn, s + pmn[x]);
		s += sum[x];
		return;
	}
	if(L == R) {
		mx = max(mx, s + pmx[x]);
		mn = min(mn, s + pmn[x]);
		s += sum[x];
		ans = sum[x] > 0 ? cap + mn : mx;
		return;
	}
	int mid = (L + R) >> 1;
	query(x * 2, L, mid);
	query(x * 2 + 1, mid + 1, R);

}
vi distribute_candies(vi c, vi l, vi r, vi v) {
	n = sz(c);
	reverse(l.begin(), l.end());
	reverse(r.begin(), r.end());
	reverse(v.begin(), v.end());
	L(i, 0, sz(l) - 1) 
		ins[l[i]].pb(i), del[r[i]].pb(i);
	vi ns(n);
	L(p, 0, sz(c) - 1) {
		for(auto&u : ins[p]) {
			modify(1, 0, sz(l) - 1, u, v[u]);
		}
		s = 0, mx = 0, mn = 0, cap = c[p], ans = -1;
		query(1, 0, sz(l) - 1);
		// L(i, 0, sz(l) - 1) {
		// 	if(l[i] <= p && p <= r[i]) {
		// 		x += v[i];
		// 		mn = min(mn, x);
		// 		mx = max(mx, x);
		// 		if(mx - mn >= c[p]) {
		// 			ans = v[i] > 0 ? c[p] + mn : mx;
		// 			break;
		// 		}
		// 	}
		// }
		if(ans == -1) ans = mx;
		ns[p] = ans;
		for(auto&u : del[p]) {
			modify(1, 0, sz(l) - 1, u, 0);
		}
	}
	return ns;
}

// int main() {
//     auto P = distribute_candies(vi{10, 15, 13}, vi{0, 0}, vi{2, 1}, vi{20, -11});
// 	for(auto&u : P) cout << u << endl;
// 	return 0;
// }