#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define INFI (ll)1000000000000000000
struct segTree{
ll l; ll r;
segTree *lc, *rc;
pair<ll, ll> mx;
pair<ll, ll> mn;
ll lazy;
segTree(ll st){
l = r = st;
lc = rc = nullptr;
mx = mn = {0, st};
lazy = 0;
}
segTree(segTree * le, segTree * ri){
lc = le; rc = ri;
mx = max(lc->mx, rc->mx);
mn = min(lc->mn, rc->mn);
lazy = 0;
l = le->l;
r = ri->r;
}
};
segTree * build (ll l, ll r){
if(l == r) return new segTree(l);
return new segTree(build(l, (l+r)/2), build((l+r)/2 + 1, r));
}
void update(ll l, ll r, ll x, segTree*st){
st->mn.first += st->lazy;
st->mx.first += st->lazy;
if(st->l != st->r){
st->lc->lazy += st->lazy;
st->rc->lazy += st->lazy;
}
st->lazy = 0;
if(st->l == st->r){
st->mn.first += x;
st->mx.first += x;
st->lazy = 0;
return;
}
if(st->l == l && st->r == r){
st->lc->lazy += x;
st->rc->lazy += x;
st->mn.first += x;
st->mx.first += x;
st->lazy = 0;
return;
}
ll mid = (st->l + st->r)/2;
if(l<=mid) update(l, min(r, mid), x, st->lc);
if(r>mid) update(max(mid+1, l), r, x, st->rc);
st->mn = min(make_pair(st->lc->mn.first + st->lc->lazy, st->lc->mn.second), {st->rc->mn.first + st->rc->lazy, st->rc->mn.second});
st->mx = max(make_pair(st->lc->mx.first + st->lc->lazy, st->lc->mx.second), {st->rc->mx.first + st->rc->lazy, st->rc->mx.second});
}
pair<ll, ll> query(ll md, ll l, ll r, segTree * st){
st->mn.first += st->lazy;
st->mx.first += st->lazy;
if(st->l != st->r){
st->lc->lazy += st->lazy;
st->rc->lazy += st->lazy;
}
st->lazy = 0;
if(st->l == st->r){
if(md == 0) return st->mn;
else return st->mx;
}
ll mid = (st->l + st->r)/2;
if(md == 0){
pair<ll, ll> ans = {INFI, INFI};
if(l <= mid) ans = min(ans, query(md, l, min(r, mid), st->lc));
if(r > mid) ans = min(ans, query(md, max(l, mid+1), r, st->rc));
return ans;
}
//if(md == 1){
pair<ll, ll> ans = {-INFI, -INFI};
if(l <= mid) ans = max(ans, query(md, l, min(r, mid), st->lc));
if(r > mid) ans = max(ans, query(md, max(l, mid+1), r, st->rc));
return ans;
//}
}
ll findMaxInd(ll c, segTree * st, pair<ll, ll> minR, pair<ll, ll> maxR){
st->mn.first += st->lazy;
st->mx.first += st->lazy;
if(st->l != st->r){
st->lc->lazy += st->lazy;
st->rc->lazy += st->lazy;
}
st->lazy = 0;
if(st->l == st->r){
return st->l;
}
if(max(maxR.first, st->rc->mx.first + st->rc->lazy) - min(st->rc->mn.first + st->rc->lazy, minR.first) >= c){
return findMaxInd(c, st->rc, minR, maxR);
}
pair<ll, ll> rMax = {st->rc->mx.first + st->rc->lazy, st->rc->mx.second};
pair<ll, ll> rMin = {st->rc->mn.first + st->rc->lazy, st->rc->mn.second};
return findMaxInd(c, st->lc, min(minR,rMin), max(maxR, rMax));
}
vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v){
ll q = v.size();
vector<pair<ll, pair<ll, ll>>> updL;
for(ll i = 0; i<q; i++){
updL.push_back({l[i], {i+2, v[i]}});
}
vector<pair<ll, pair<ll, ll>>> updR;
for(ll i = 0; i<q; i++){
updR.push_back({r[i], {i+2, v[i]}});
}
sort(updL.begin(), updL.end());
sort(updR.begin(), updR.end());
segTree * st = build(0, q+1);
update(0, 0, INFI, st);
vector<int> ans;
for(ll i = 0; i<C.size(); i++){
ll c = C[i];
ll le = upper_bound(updL.begin(), updL.end(), make_pair(i-1, make_pair(INFI, INFI))) - updL.begin();
ll ri = upper_bound(updL.begin(), updL.end(), make_pair(i, make_pair(INFI, INFI))) - updL.begin()-1;
for(ll j = le; j<=ri; j++) update(updL[j].second.first, q+1, updL[j].second.second, st);
le = upper_bound(updR.begin(), updR.end(), make_pair(i-2, make_pair(INFI, INFI))) - updR.begin();
ri = upper_bound(updR.begin(), updR.end(), make_pair(i-1, make_pair(INFI, INFI))) - updR.begin()-1;
for(ll j = le; j<=ri; j++) update(updR[j].second.first, q+1, -updR[j].second.second, st);
le = findMaxInd(c, st, {INFI, INFI}, {-INFI, -INFI});
auto maxInRange = query(1, le, q+1, st);
auto minInRange = query(0, le, q+1, st);
if(maxInRange.second > minInRange.second) ans.push_back(query(0, q+1, q+1, st).first - query(0, maxInRange.second, maxInRange.second, st).first + c);
else ans.push_back(query(0, q+1, q+1, st).first - query(0, minInRange.second, minInRange.second, st).first);
}
return ans;
}
