#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#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 all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
#include "candies.h"
struct segtree{
ll N=1;
vp seg;
vi lazy;
P f(P a,P b){
return P(max(a.fi,b.fi),min(a.se,b.se));
}
segtree(ll n){
while(N<n)N<<=1;
seg=vp(N*2,P(-inf,inf));lazy=vi(N*2);
rep(i,n)seg[i+N]=P(0,0);
for(ll i=N-1;i>0;i--)seg[i]=f(seg[i*2],seg[i*2+1]);
}
void eval(ll k,ll l,ll r){
seg[k].fi+=lazy[k];seg[k].se+=lazy[k];
if(r-l>1){
lazy[k*2]+=lazy[k];
lazy[k*2+1]+=lazy[k];
}
lazy[k]=0;
}
void add(ll x,ll a,ll b,ll k=1,ll l=0,ll r=-1){
if(r==-1)r=N;
if(a<=l&&r<=b){
lazy[k]+=x;
eval(k,l,r);
return;
}
if(r<=a||b<=l){
eval(k,l,r);return;
}
eval(k,l,r);
add(x,a,b,k*2,l,(l+r)/2);
add(x,a,b,k*2+1,(l+r)/2,r);
seg[k]=f(seg[k*2],seg[k*2+1]);
}
P get(ll a,ll b,ll k,ll l,ll r){
if(a<=l&&r<=b){
eval(k,l,r);
return seg[k];
}
if(r<=a||b<=l)return P(-inf,inf);
eval(k,l,r);
return f(get(a,b,k*2,l,(l+r)/2),get(a,b,k*2+1,(l+r)/2,r));
}
ll getma(ll a,ll b){
return get(a,b,1,0,N).fi;
}
ll getmi(ll a,ll b){
return get(a,b,1,0,N).se;
}
ll getdif(ll a,ll b){
P res=get(a,b,1,0,N);
return res.fi-res.se;
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
ll n=c.size(),q=v.size();
vvp event(n+1);
rep(i,q){
event[l[i]].pb(q-i,-v[i]);
event[r[i]+1].pb(q-i,v[i]);
}
segtree seg(q+1);
vector<int> res(n);
rep(i,n){
for(P x:event[i])seg.add(x.se,x.fi,q+1);
ll ok=q+1,ng=-1;
while(ok-ng>1){
ll md=(ok+ng)/2;
if(seg.getdif(0,md+1)>=c[i])ok=md;
else ng=md;
}
if(ok==q+1||seg.getma(0,ok+1)==seg.getma(ok,ok+1))res[i]=-seg.getmi(0,ok+1);
else res[i]=c[i]-seg.getma(0,ok+1);
}
return res;
}
