#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MN = 2e5 + 5;
const ll inf = 1e16;
struct def{
ll mx , mn;
};
int n , q;
ll lz[MN * 4];
vector<def> t(MN * 4);
def kur;
def mrg(def a , def b){
return {max(a.mx , b.mx) , min(a.mn , b.mn)};
}
void push(int v){
if(! lz[v]) return ;
lz[v * 2] += lz[v];
t[v * 2] = {t[v * 2].mx + lz[v] , t[v * 2].mn + lz[v]};
lz[v * 2 + 1] += lz[v];
t[v * 2 + 1] = {t[v * 2 + 1].mx + lz[v] , t[v * 2 + 1].mn + lz[v]};
lz[v] = 0;
}
void upd(int v , int l , int r , int l1 , int r1 , int val){
if(l <= l1 and r1 <= r){
lz[v] += val;
t[v] = {t[v].mx + val , t[v].mn + val};
return ;
}
if(r1 - l1 > 1) push(v);
int m = (l1 + r1) / 2;
if(l1 < r and l < m) upd(v * 2 , l , r , l1 , m , val);
if(m < r and l < r1) upd(v * 2 + 1 , l , r , m , r1 , val);
t[v] = mrg(t[v * 2] , t[v * 2 + 1]);
}
int get(int v , int l , int r , ll dif){
if(r - l == 1) return l;
push(v);
def nk = mrg(t[v * 2 + 1] , kur);
int m = (l + r) / 2;
if(nk.mx - nk.mn <= dif){
kur = nk;
return get(v * 2 , l , m , dif);
}
else return get(v * 2 + 1 , m , r , dif);
}
int gett(int dif){
kur = {-inf , inf};
return get(1 , 0 , q + 1 , dif);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v){
n = c.size() , q = l.size();
vector<int> ans(n , 0);
vector<int> iv[n + 1];
for(int i = 0;i < q; ++ i){
iv[l[i]].push_back(i);
iv[r[i] + 1].push_back(i);
}
ll height = 0;
for(int i = 0;i < n; ++ i){
for(auto to : iv[i]){
if(l[to] == i){
upd(1 , to + 1 , q + 1 , 0 , q + 1 , v[to]);
height += v[to];
}
else{
upd(1 , to + 1 , q + 1 , 0 , q + 1 , -v[to]);
height -= v[to];
}
}
if(t[1].mx - t[1].mn <= c[i]) ans[i] = (height - t[1].mn);
else{
int ps = gett(c[i]);
//cout << ps << ' ' << i << '\n';
if(v[ps] > 0){
ans[i] = height - (kur.mx - c[i]);
}
else{
ans[i] = height - kur.mn;
}
}
}
return ans;
}
