#include <iostream>
#include <vector>
using namespace std;
#define ll long long
const int N = 1<<18;
ll Mx[N<<1], Mn[N<<1], D1[N<<1], Lz[N<<1];
ll inf = 1e16;
vector<int> L[N], R[N];
void Push(int cur, int lc, int rc){
Mx[lc] += Lz[cur], Mn[lc] += Lz[cur], Lz[lc] += Lz[cur];
Mx[rc] += Lz[cur], Mn[rc] += Lz[cur], Lz[rc] += Lz[cur];
Lz[cur] = 0;
}
void Add(int l, int r, ll v, int cur = 1, int st = 0, int en = N){
if (l >= en or r <= st)
return;
if (l <= st and r >= en){
Mx[cur] += v;
Mn[cur] += v;
Lz[cur] += v;
return;
}
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc);
Add(l, r, v, lc, st, mid);
Add(l, r, v, rc, mid, en);
Mx[cur] = max(Mx[lc], Mx[rc]);
Mn[cur] = min(Mn[lc], Mn[rc]);
D1[cur] = max(Mx[rc] - Mn[lc], max(D1[lc], D1[rc]));
}
int getInd(int v, ll M = -inf, int cur = 1, int st = 0, int en = N){
if (en - st == 1)
return st;
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc);
if (D1[rc] >= v or M - Mn[rc] >= v)
return getInd(v, M, rc, mid, en);
return getInd(v, max(M, Mx[rc]), lc, st, mid);
}
ll getMin(int l, int r, int cur = 1, int st = 0, int en = N){
if (l >= en or r <= st)
return inf;
if (l <= st and r >= en)
return Mn[cur];
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc);
return min(getMin(l, r, lc, st, mid), getMin(l, r, rc, mid, en));
}
ll getMax(int l, int r, int cur = 1, int st = 0, int en = N){
if (l >= en or r <= st)
return -inf;
if (l <= st and r >= en)
return Mx[cur];
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc);
return max(getMax(l, r, lc, st, mid), getMax(l, r, rc, mid, en));
}
ll val(int i, ll ans = 0){
for (i += N; i ; i /= 2)
ans += Lz[i];
return ans;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
int n = c.size(), q = l.size();
Add(q + 1, N, -inf);
for (int i=0;i<q;i++){
L[l[i]].push_back(i);
R[r[i]].push_back(i);
}
vector<int> ans;
for (int i=0;i<n;i++){
for (int I : L[i])
Add(I+1, q + 1, v[I]);
if (D1[1] < c[i]){
ll mn = getMin(0, q + 1);
ans.push_back(val(q) - mn);
}
else{
int i1 = getInd(c[i]);
ll mx = getMax(i1+1, q+1);
ll mn = getMin(i1+1, q+1);
if (mx - mn >= c[i])
ans.push_back(val(q) - mn);
else
ans.push_back(val(q) - mx + c[i]);
}
for (int I : R[i])
Add(I+1, q + 1, -v[I]);
}
return ans;
}
