#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=2e5+9;
const ll INF=1e18;
struct Nodo{
ll mn=0,mx=0,lz=0;
};
Nodo st[MAXN*4];
int n,q;
void appl(int v,ll x){
st[v].mn+=x;
st[v].mx+=x;
st[v].lz+=x;
}
void push(int v){
appl(v*2,st[v].lz);
appl(v*2+1,st[v].lz);
st[v].lz=0;
}
void upd(int ts,int te,ll x,int v=1,int s=0,int e=q){
if(e<ts||te<s)return;
if(ts<=s&&e<=te){
appl(v,x);
return;
}else{
push(v);
int m=(s+e)/2;
upd(ts,te,x,v*2,s,m);
upd(ts,te,x,v*2+1,m+1,e);
st[v].mn=min(st[v*2].mn,st[v*2+1].mn);
st[v].mx=max(st[v*2].mx,st[v*2+1].mx);
}
}
pair<ll,ll> que(int ts,int te,int v=1,int s=0,int e=q){
if(e<ts||te<s)return pair<ll,ll>{INF,-INF};
if(ts<=s&&e<=te){
return pair<ll,ll>{st[v].mn,st[v].mx};
}else{
push(v);
int m=(s+e)/2;
pair<ll,ll> a=que(ts,te,v*2,s,m);
pair<ll,ll> b=que(ts,te,v*2+1,m+1,e);
return pair<ll,ll>{min(a.fst,b.fst),max(a.snd,b.snd)};
}
}
ll get(int i){
return que(i,i).snd;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n=SZ(c),q=SZ(l);
vector<vector<pair<ll,ll>>>ty(n);
fore(i,0,q){
ty[l[i]].emplace_back(i+1,v[i]);
if(r[i]+1<n)ty[r[i]+1].emplace_back(i+1,-v[i]);
}
vector<int>ret(n);
fore(i,0,n){
fore(j,0,SZ(ty[i])){
upd(ty[i][j].fst,q,ty[i][j].snd);
}
ll sum=get(q);
if(st[1].mx-st[1].mn<=c[i]){
ret[i]=sum-st[1].mn;
continue;
}
int L=0,R=q+1;
while(R-L>1){
int m=(L+R)/2;
pair<ll,ll> a=que(m,q);
if(a.snd-a.fst>=c[i]){
L=m;
}else R=m;
}
if(get(L)<=sum){
ret[i]=(ll)c[i]-(que(L,q).snd-sum);
}else{
ret[i]=sum-que(L,q).fst;
}
}
return ret;
}
