#include <bits/stdc++.h>
#include <cassert>
#include "candies.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
const ll INF = 2e18;
struct SegTree{
struct node{
ll mx, mn, mxi, mni, add;
node(){
mx=mn=mxi=mni=add=0;
}
node(bool neutral){
mx=-INF; mn=INF; mxi=-1; mni=-1; add=0;
}
};
vector<node> t; ll rsz;
SegTree(ll N){
rsz=N; t.resize(N*4);
build(0, rsz-1, 1);
}
void preprocess(ll tl, ll tr, ll v){
if (t[v].add){
t[v].mn+=t[v].add;
t[v].mx+=t[v].add;
if (tl!=tr){
t[v*2].add+=t[v].add;
t[v*2+1].add+=t[v].add;
}
t[v].add=0;
}
}
node merge(node l, node r){
node nw;
nw.mxi=(l.mx>=r.mx?l.mxi:r.mxi);
nw.mni=(l.mn<=r.mn?l.mni:r.mni);
nw.mx=max(l.mx, r.mx);
nw.mn=min(l.mn, r.mn);
return nw;
}
void build(ll tl, ll tr, ll v){
if (tl==tr){
t[v].mxi=t[v].mni=tl;
}else{
ll tm = (tl+tr)/2;
build(tl, tm, v*2);
build(tm+1, tr, v*2+1);
t[v]=merge(t[v*2], t[v*2+1]);
}
}
void update(ll tl, ll tr, ll v, ll l, ll r, ll x){
preprocess(tl, tr, v);
if (tl==l and tr==r){
t[v].add+=x;
preprocess(tl, tr, v);
}else if (l>r) return;
else{
ll tm = (tl+tr)/2;
update(tl, tm, v*2, l, min(r, tm), x);
update(tm+1, tr, v*2+1, max(l, tm+1), r, x);
t[v]=merge(t[v*2], t[v*2+1]);
}
}
void update(ll l, ll r, ll x){
update(0, rsz-1, 1, l, r, x);
}
ll queryLeft(ll tl, ll tr, ll v, ll delta, ll smx, ll smn){
preprocess(tl, tr, v);
if (tl==tr){
// cout << tl << " - " << tr << " | " << rsz-1 << " ~ ";
// cout << delta << " -> " << max(smx, t[v].mx) << " - " << min(smn, t[v].mn) << endl;
return ((max(smx, t[v].mx)-min(smn, t[v].mn))>=delta?tl:-1);
}else{
ll tm = (tl+tr)/2;
preprocess(tl, tm, v*2);
preprocess(tm+1, tr, v*2+1);
if (max(smx, t[v*2+1].mx)-min(smn, t[v*2+1].mn)>=delta) return queryLeft(tm+1, tr, v*2+1, delta, smx, smn);
else return queryLeft(tl, tm, v*2, delta, max(smx, t[v*2+1].mx), min(smn, t[v*2+1].mn));
}
}
ll queryLeft(ll delta){
return queryLeft(0, rsz-1, 1, delta, -INF, INF);
}
node query(ll tl, ll tr, ll v, ll l, ll r){
preprocess(tl, tr, v);
if (tl==l and tr==r){
return t[v];
}else if (l>r) return node(0);
else{
ll tm = (tl+tr)/2;
return merge(query(tl, tm, v*2, l, min(r, tm)), query(tm+1, tr, v*2+1, max(l, tm+1), r));
}
}
array<ll, 3> query(ll l, ll r){
node ret=query(0, rsz-1, 1, l, r);
return {ret.mni, ret.mxi, ret.mn};
}
ll pquery(ll tl, ll tr, ll v, ll i){
preprocess(tl, tr, v);
if (tl==tr){
assert(t[v].mx==t[v].mn);
return t[v].mx;
}else{
ll tm = (tl+tr)/2;
if (i<=tm) return pquery(tl, tm, v*2, i);
else return pquery(tm+1, tr, v*2+1, i);
}
}
ll pquery(ll i){
return pquery(0, rsz-1, 1, i);
}
void debug(){
cout << "Debuggin: " << t[1].mn << " " << t[1].mx << endl;
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), q=l.size();
vector<vector<array<ll, 3>>> sweep(n);
for (ll i=0; i<q; i++){
sweep[l[i]].push_back({i+1, v[i], 0});
sweep[r[i]].push_back({i+1, v[i], 1});
}
vector<int> res(n);
SegTree tr(q+1);
for (ll i=0; i<n; i++){
for (auto [j, d, typ]:sweep[i]){
if (typ==0){
// cout << j << " + " << d << endl;
tr.update(j, q, d);
}
}
// tr.debug();
// cout << "Here" << endl;
ll ind = tr.queryLeft(c[i]);
// cout << "Here: " << ind << endl;
if (ind==-1){
array<ll, 3> bound = tr.query(0, q);
res[i] = tr.pquery(q)+abs(bound[2]);
}else{
array<ll, 3> bound = tr.query(ind, q);
// cout << ind << " - " << bound[0] << " & " << bound[1] << "&" << bound[2] << endl;
if (bound[0]>=bound[1]){
res[i] = tr.pquery(q)-tr.pquery(bound[0]);
}else{
res[i] = tr.pquery(q)-tr.pquery(bound[1])+c[i];
}
}
// cout << "Here" << endl;
// cout << "not Here" << endl;
for (auto [j, d, typ]:sweep[i]){
if (typ==1){
tr.update(j, q, -d);
}
}
}
return res;
}
