#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
using namespace std;
const int N = 3e5 + 1;
typedef long long ll;
int n,q;
vector<ll> add[N],del[N];
ll t[N * 4],mod[N * 4];
pair<ll,ll> mx[N * 4],mn[N * 4];
void merge(int v){
t[v] = t[v + v] + t[v + v + 1];
mx[v] = max(mx[v + v],mx[v + v + 1]);
if(mn[v + v].first != mn[v + v + 1].first){
mn[v] = min(mn[v + v],mn[v + v +1]);
}else{
mn[v] = max(mn[v + v],mn[v + v + 1]);
}
}
void build(int v = 1,int tl = 0,int tr = q){
if(tl == tr){
mx[v] = mn[v] = {0,tl};
}else{
int tm = (tl + tr) >> 1;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
merge(v);
}
}
void inc(int v,ll val){
t[v] += val;
mn[v].first += val;
mx[v].first += val;
mod[v] += val;
}
void push(int v){
if(mod[v] &&v + v + 1 < N *4){
inc(v + v,mod[v]);
inc(v + v + 1,mod[v]);
mod[v] = 0;
}
}
void upd(int l,int r,ll val,int v = 1,int tl = 0,int tr = q){
if(l > r || tl > r || l > tr)return;
if(tl >= l && tr <= r){
inc(v,val);
}else{
push(v);
int tm = (tl + tr) >> 1;
upd(l,r,val,v+v,tl,tm);
upd(l,r,val,v+v+1,tm+1,tr);
merge(v);
}
}
const ll inf = 1e18;
pair<ll,ll> get_max(int l,int r,int v = 1,int tl =0 ,int tr = q){
if(l > r || tl > r || l > tr) return {-inf,-inf};
if(tl >= l && tr <= r) return mx[v];
push(v);
int tm = (tl + tr) >> 1;
return max(get_max(l,r,v+v,tl,tm),get_max(l,r,v+v+1,tm+1,tr));
}
pair<ll,ll> get_min(int l,int r,int v = 1,int tl =0 ,int tr = q){
if(l > r || tl > r || l > tr) return {inf,inf};
if(tl >= l && tr <= r) return mn[v];
push(v);
int tm = (tl + tr) >> 1;
pair<ll,ll> L = get_min(l,r,v+v,tl,tm),R = get_min(l,r,v+v+1,tm+1,tr);
if(L.first != R.first){
return min(L,R);
}
return max(L,R);
}
ll get_sum(int l,int r,int v = 1,int tl = 0,int tr = q){
if(l > r || tl > r || l > tr) return 0ll;
if(tl >= l && tr <= r) return t[v];
push(v);
int tm = (tl + tr) >> 1;
return get_sum(l,r,v+v,tl,tm)+get_sum(l,r,v+v+1,tm+1,tr);
}
bool ok(int i,int c){
return (get_max(i,q).first - get_min(i,q).first > c);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v){
n = (int)c.size();
q = (int)l.size();
build();
for(int i = 0;i < q;i++){
add[l[i]].push_back(i);
del[r[i]].push_back(i);
}
vector<int> ret;
int col = 0;
for(int i = 0;i < n;i++){
for(int j:add[i]){
upd(j + 1,q,v[j]);
}
ll all = get_sum(q,q);
if(mx[1].first - mn[1].first <= c[i]){
ret.push_back(get_sum(q,q)-mn[1].first);
}else{
int L = 0,R = q;
while(R - L > 1){
int mid = (L + R) >> 1;
if(ok(mid,c[i])){
L = mid;
}else R = mid;
}
ll val = get_sum(L,L);
pair<ll,ll> f = get_max(L,q),s = get_min(L,q);
if(f.second > s.second){
ret.push_back(c[i] - (f.first - all));
}else{
ret.push_back(all - s.first);
}
}
for(int j:del[i]){
upd(j + 1,q,-v[j]);
}
}
return ret;
}
