#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
struct segtree{
ll n;
vector<PP> seg;
segtree(ll n_):n(n_),seg(n_*2){}
PP f(PP a,PP b){
chmax(get<1>(a),get<0>(a)+get<1>(b));
chmin(get<2>(a),get<0>(a)+get<2>(b));
get<0>(a)+=get<0>(b);
return a;
}
void update(ll i,PP x){
seg[i+n]=x;
}
PP rng(ll l,ll r){
PP res(0,0,0);
REP(i,l,r)res=f(res,seg[i+n]);
return res;
}
void debug(){
rep(i,n)cout<<'('<<get<0>(seg[i+n])<<','<<get<1>(seg[i+n])<<','<<get<2>(seg[i+n])<<')';
cout<<endl;
}
};
vector<int> distribute_candies(vector<int> C, vector<int> L,vector<int> R, vector<int> V) {
ll n=C.size(),q=L.size();
vi c(n),l(q),r(q),v(q);
rep(i,n)c[i]=C[i];
rep(i,q)l[i]=L[q-i-1];
rep(i,q)r[i]=R[q-i-1]+1;
rep(i,q)v[i]=-V[q-i-1];
vvi add(n+1),ers(n+1);
rep(i,q){
add[l[i]].pb(i);ers[r[i]].pb(i);
}
segtree seg(q);
vector<int> res(n);
rep(i,n){
for(ll x:add[i])seg.update(x,PP(v[x],max(0ll,v[x]),min(0ll,v[x])));
for(ll x:ers[i])seg.update(x,PP(0,0,0));
// out(c[i]);
// seg.debug();
ll ok=0,ng=q+1;
while(ng-ok>1){
ll md=(ok+ng)/2;
auto tmp=seg.rng(0,md);
if(get<1>(tmp)-get<2>(tmp)>c[i])ng=md;
else ok=md;
}
if(ok==q)res[i]=-get<2>(seg.rng(0,q));
else if(get<0>(seg.rng(0,ng))<0)res[i]=c[i]-get<1>(seg.rng(0,ng));
else res[i]=-get<2>(seg.rng(0,ng));
}
return res;
}
