#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
ll C;
struct Trans {
ll l = 0, y = 0, r = C;
};
void merge(Trans &a, Trans b) {
ll l = max(a.l, b.l - a.y + a.l);
ll y;
if (a.y <= b.l)
y = b.y;
else if (a.y <= b.r)
y = a.y - b.l + b.y;
else
y = b.r - b.l + b.y;
ll r = min(a.r, b.r - a.y + a.l);
if (r <= l)
l = r = 0;
a = {l, y, r};
}
void add(Trans &a, ll x) {
merge(a, {max(0ll, -x), max(x, 0ll), min(C, C - x)});
}
struct Tree {
ll base;
vc<Trans> t;
Tree() = default;
Tree(ll size) {
base = 1;
while (base < size)
base *= 2;
t.assign(2 * base, {0, 0, C});
}
void push(ll i, ll li, ll ri) {
merge(t[li], t[i]);
merge(t[ri], t[i]);
t[i] = {0, 0, C};
}
void update(ll ql, ll qr, ll qx, ll i = 1, ll l = 0, ll r = -1) {
if (r == -1)
r = base - 1;
if (qr < l or r < ql)
return;
if (ql <= l and r <= qr) {
add(t[i], qx);
return;
}
ll m = (l + r) / 2;
ll li = 2 * i;
ll ri = li + 1;
push(i, li, ri);
update(ql, qr, qx, li, l, m);
update(ql, qr, qx, ri, m + 1, r);
}
void pushAll() {
for (ll i = 1; i < base; i++)
push(i, 2 * i, 2 * i + 1);
}
};
ll n, q;
vc<ll> cap, ql, qr, qx, res;
void program() {
Tree tree(n);
for (ll i = 0; i < q; i++)
tree.update(ql[i], qr[i], qx[i]);
tree.pushAll();
res.resize(n);
for (ll i = 0; i < n; i++)
res[i] = tree.t[i + tree.base].y;
}
vc<int> distribute_candies(vc<int> c, vc<int> l, vc<int> r, vc<int> v) {
n = sz(c);
q = sz(l);
cap.assign(all(c));
C = cap[0];
ql.assign(all(l));
qr.assign(all(r));
qx.assign(all(v));
program();
vc<int> ret(all(res));
return ret;
}
