#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ST {
struct R {
ll mn, mx;
R() : mn(1ll<<60), mx(-(1ll<<60)) {}
R(int x) : mn(x), mx(x) {}
};
int n;
vector<R> st;
vector<ll> lazy;
ST(int sz) : n(sz), st(4*n,0), lazy(4*n,0) {}
R mer(R a, R b){
R c;
c.mn = min(a.mn,b.mn);
c.mx = max(a.mx,b.mx);
return c;
}
void push(int p){
st[p].mn+=lazy[p];
st[p].mx+=lazy[p];
if((p<<1|1) < 4*n){
lazy[p<<1]+=lazy[p];
lazy[p<<1|1]+=lazy[p];
}
lazy[p] = 0;
}
void update(int i, int j, ll v, int l, int r, int p){
push(p);
if(l >= i && r <= j){
lazy[p]+=v;
push(p);
return;
}
if(l > j || r < i)return;
int m = (l+r)>>1;
update(i,j,v,l,m,p<<1);
update(i,j,v,m+1,r,p<<1|1);
st[p] = mer(st[p<<1],st[p<<1|1]);
}
R que(int i, int j, int l, int r, int p){
push(p);
if(l >= i && r <= j)return st[p];
if(l > j || r < i)return R();
int m = (l+r)>>1;
return mer(que(i,j,l,m,p<<1), que(i,j,m+1,r,p<<1|1));
}
};
struct T {
ll x, i;
T(int _x, int _i) : x(_x), i(_i) {}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
int q = l.size();
vector<vector<T>> am(n+1);
for(int i = 0; i < q; ++i){
am[l[i]].emplace_back(v[i],i+1);
am[r[i]+1].emplace_back(-v[i],i+1);
}
ST S(q+1);
vector<int> ans(n,0);
for(int i = 0; i < n; ++i){
for(auto x : am[i]){
S.update(x.i,q,x.x,0,q,1);
}
ll a = -(1ll<<60), b = (1ll<<60);
int l = 0, r = q;
while(l <= r){
int m = (l+r) >> 1;
auto x = S.que(m,q,0,q,1);
if(x.mx-x.mn >= c[i]){
a = max(a,x.mn);
b = min(b,x.mx);
l = m+1;
}
else {
r = m-1;
}
}
auto x = S.que(l,q,0,q,1);
if(l == 0){
a = x.mn, b = c[i]-x.mn;
}
if(x.mn == a)ans[i] = (int)(S.que(q,q,0,q,1).mn-a);
else ans[i] = (int)(c[i] - (b - S.que(q,q,0,q,1).mn));
}
return ans;
}
