#include<bits/stdc++.h>
#include "candies.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,C[200009],f[200009],tes,t,L[200009],R[200009],V[200009],T=300;
int lf[200009],rg[200009],le[200009],ri[200009];
int fun(int q){
return (q-1)/T+1;
}
void reDO(int q){
//cout<<"Test:"<<t<<" "<<q<<endl;
int mi=C[1]+3,qw=0,we=0;
for(int h=(q-1)*T+1; h<=min(a,q*T); h++){
mi=min(mi,f[h]);
}
for(int h=(q-1)*T+1; h<=min(a,q*T); h++){
qw=f[h]-mi;
if(qw<=le[q]){
f[h]=lf[q];
}else{
qw-=le[q];
f[h]=min(lf[q]+qw,rg[q]);
}
}
for(int h=(q-1)*T+1; h<=min(a,q*T); h++){
if(h<L[t]||h>R[t]) continue;
f[h]+=V[t];
if(f[h]<0) f[h]=0;if(f[h]>C[1]) f[h]=C[1];
}
le[q]=0;ri[q]=0;lf[q]=C[1]+3;rg[q]=0;
for(int h=(q-1)*T+1; h<=min(q*T,a); h++){
lf[q]=min(lf[q],f[h]);rg[q]=max(rg[q],f[h]);
}
}
vector<int> distribute_candies(vector<int> Cc, vector<int> Ll, vector<int> Rr, vector<int> Vv) {
a=Cc.size();tes=Ll.size();
for(i=1; i<=a; i++) C[i]=Cc[i-1];
for(t=1; t<=tes; t++){
L[t]=Ll[t-1]+1;R[t]=Rr[t-1]+1;V[t]=Vv[t-1];
}
for(t=1; t<=tes; t++){
i=fun(L[t])+1;i=(i-1)*T+1;
for( ; i<=a; i+=T){
if(fun(i)>=fun(R[t])) break;
ii=fun(i);
if(V[t]>0){
if(rg[ii]+V[t]<=C[1]){
lf[ii]+=V[t];rg[ii]+=V[t];
}else{
ri[ii]+=min(rg[ii]-lf[ii],V[t]-(C[1]-rg[ii]));
lf[ii]=min(lf[ii]+V[t],C[1]);rg[ii]=C[1];
}
}else{
if(lf[ii]+V[t]>=0){
lf[ii]+=V[t];rg[ii]+=V[t];
}else{
le[ii]+=min(rg[ii]-lf[ii],-V[t]-lf[ii]);
lf[ii]=0;rg[ii]=max(rg[ii]+V[t],0);
}
}
}
ii=fun(L[t]);
reDO(ii);
if(ii!=fun(R[t])){
ii=fun(R[t]);
reDO(ii);
}
}
for(ii=1; ; ii++){
if((ii-1)*T+1>a) break;
reDO(ii);
}
vector <int> ANS;
for(i=1; i<=a; i++){
ANS.push_back(f[i]);
}
return ANS;
}
