#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll, ll> prll;
typedef set<ll> setll;
typedef map<ll,ll> mapll;
#define uset unordered_set
typedef uset<ll> usetll;
#define umap unordered_map
typedef umap<ll,ll> umapll;
#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define fi first
#define se second
#define sz size
#define all(x) (x).begin(), (x).end()
#define all0(x, n) (x).begin(), (x).begin()+n
#define all1(x, n) (x).begin()+1, (x).begin()+n+1
#define allrev(x) (x).rbegin(), (x).rend()
#define in(v, s) ((s).find((v)) != (s).end())
#define GCD(x, y) __gcd(abs((x)), abs((y)))
#define INF (LLONG_MAX>>3ll)
#define MOD (1'000'000'007ll)
#define mxN (200'010ll)
#define sgN (1ll<<18ll)
#define mxQ (200'010ll)
inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }
inline void print (vcll &a, ll n=-1, string name="")
{
cout << name << ": ";
if (n==-1) for (ll x:a) printf("%lli ", x);
else
{
ll i;
f0r(i,1,n) printf("%lli ", a[i]);
}
printf("\n");
}
ll n, q;
vcll C(mxN), L(mxQ), R(mxQ), X(mxQ);
vc<vc<prll>> qs(mxN);
struct ST
{
struct nd
{
ll mx, mn, s, lz;
inline nd() { mx=mn=s=lz=0; }
};
vc<nd> st;
inline ST() { st.resize(sgN*2+10); }
inline void prop (ll it, ll lt, ll rt)
{
ll lz=st[it].lz;
st[it].lz=0;
st[it].mx+=lz;
st[it].mn+=lz;
st[it].s+=lz*(rt-lt);
if (lt+1==rt) return;
ll i2=it*2;
st[i2].lz+=lz;
st[i2+1].lz+=lz;
}
ll minp (ll it, ll lt, ll rt, ll l, ll r)
{
prop(it,lt,rt);
if (rt<=l or r<=lt) return INF;
if (l<=lt and rt<=r) return st[it].mn;
ll i2=it*2, mt=(lt+rt)/2;
return min( minp(i2,lt,mt,l,r), minp(i2+1,mt,rt,l,r));
}
inline ll minp (ll l, ll r) { return minp(1,0,q+1,l,r+1); }
ll maxp (ll it, ll lt, ll rt, ll l, ll r)
{
prop(it,lt,rt);
if (rt<=l or r<=lt) return -INF;
if (l<=lt and rt<=r) return st[it].mx;
ll i2=it*2, mt=(lt+rt)/2;
return max( maxp(i2,lt,mt,l,r), maxp(i2+1,mt,rt,l,r));
}
inline ll maxp (ll l, ll r) { return maxp(1,0,q+1,l,r+1); }
ll acc (ll it, ll lt, ll rt, ll j) // works with min
{
prop(it,lt,rt);
if (rt<=j or j<lt) return INF;
if (lt+1==rt) return st[it].mn;
ll i2=it*2, mt=(lt+rt)/2;
return min( acc (i2,lt,mt,j), acc(i2+1,mt,rt,j));
}
inline ll acc (ll j) { return acc(1,0,q+1,j); }
ll maxl (ll it, ll lt, ll rt, ll c, ll mx, ll mn)
{
// printf("it: %lli, lt: %lli, rt: %lli, c: %lli, st.mx: %lli, st.mn: %lli, mx: %lli, mn: %lli\n", it, lt, rt, c, st[it].mx, st[it].mn, mx, mn);
prop(it,lt,rt);
if (max(mx,st[it].mx)-min(mn,st[it].mn) < c) return -1;
if (lt+1==rt) return lt;
ll i2=it*2, mt=(lt+rt)/2;
ll res=maxl(i2+1,mt,rt,c,mx,mn);
if (res!=-1) return res;
return maxl(i2,lt,mt,c, max(mx,st[i2+1].mx), min(mn,st[i2+1].mn));
}
inline ll maxl (ll c) { return maxl (1,0,q+1,c,-INF,INF); }
inline void merge (ll it, ll lt, ll rt)
{
ll i2=it*2;
st[it].mx = max(st[i2].mx, st[i2+1].mx);
st[it].mn = min(st[i2].mn, st[i2+1].mn);
st[it].s = st[i2].s + st[i2+1].s;
}
void upd (ll it, ll lt, ll rt, ll l, ll r, ll x)
{
prop(it,lt,rt);
if (rt<=l or r<=lt) return;
if (l<=lt and rt<=r)
{
st[it].lz+=x;
prop(it,lt,rt);
return;
}
ll i2=it*2, mt=(lt+rt)/2;
upd (i2,lt,mt,l,r,x);
upd (i2+1,mt,rt,l,r,x);
merge(it,lt,rt);
}
inline void upd (ll l, ll r, ll x) { upd (1,0,q+1,l,r+1,x); }
} st;
inline void upd (ll i, ll x) { st.upd(i,q,x); }
inline bool case1 (ll l, ll c)
{
ll pr=st.maxp(l,q), pl=st.acc(l);
return pr-pl>=c;
}
inline ll qry (ll c)
{
// printf("c: %lli\n", c);
ll l=st.maxl(c);
// printf("l: %lli\n", l);
if (case1(l,c))
{
// printf("case1\n");
ll pn=st.acc(q), pr=st.maxp(l,q);
return c+pn-pr;
}
else
{
// printf("case2\n");
ll pn=st.acc(q), pr=st.minp(l,q);
return pn-pr;
}
}
inline void bd_qs()
{
ll i;
f0r(i,1,q)
{
ll l=L[i], r=R[i], x=X[i];
qs[l].pb({i,x});
qs[r+1].pb({i,-x});
}
}
vc<int> distribute_candies(vc<int> C1, vc<int> L1, vc<int> R1, vc<int> X1)
{
n=C1.sz(); q=L1.sz();
ll i;
f0r(i,1,n) C[i]=C1[i-1];
f0r(i,1,q)
{
L[i]=L1[i-1]+1;
R[i]=R1[i-1]+1;
X[i]=X1[i-1];
}
bd_qs();
vc<int> ans;
f0r(i,1,n)
{
for (prll jx:qs[i]) upd(jx.fi, jx.se);
ans.pb(qry(C[i]));
}
return ans;
}
