#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
int CONS;
vector<int>ans;
struct segtree{
struct DATA{
int mx,mn,add;
DATA(){
mx=1e9;
mn=0;
add=0;
}
DATA(int a,int b,int c){
mx=a,mn=b,add=c;
}
void apply(DATA k){
mx+=k.add,mn+=k.add,add+=k.add;
mx=min(mx,k.mx),mn=min(mn,k.mx);
mx=max(mx,k.mn),mn=max(mn,k.mn);
add=min(max(add,-CONS),CONS);
}
} T[1<<19];
void pd(int i){
T[i*2].apply(T[i]);
T[i*2+1].apply(T[i]);
T[i]=DATA();
}
void upd(int i,int l,int r,int ll,int rr,int v){
if(ll<=l&&r<=rr)
return T[i].apply((DATA){CONS,0,v});
if(ll>r||l>rr) return;
pd(i);upd(i*2,l,l+r>>1,ll,rr,v);
upd(i*2+1,l+r+2>>1,r,ll,rr,v);
}
void traverse(int i,int l,int r){ if(l==r)
return ans.push_back(max(T[i].mn,min(T[i].mx,T[i].add)));
pd(i);traverse(i*2,l,l+r>>1);
traverse(i*2+1,l+r+2>>1,r);
}
} seg;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
CONS=c[0];
int n = c.size(),q=l.size();
for(int i=0;i<q;i++)
seg.upd(1,0,n-1,l[i],r[i],v[i]);
seg.traverse(1,0,n-1);
return ans;
}
