#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;
inline pii fzmax(pii p1, pii p2) {
if (p1.first>p2.first) {
return p1;
}
return p2;
}
inline pii fzmin(pii p1, pii p2) {
if (p1.first<p2.first) {
return p1;
}
return p2;
}
inline ll v2(ll x) {
return __builtin_ctz(x);
}
const ll Nm = 262144; const ll E = 18;
ll minv[2*Nm];
ll minl[2*Nm];
ll maxv[2*Nm];
ll maxl[2*Nm];
ll lz[2*Nm]; //ALREADY APPLIED
void init() {
for (ll i=0;i<(2*Nm);i++) {
minv[i]=0;
maxv[i]=0;
lz[i]=0;
}
for (ll i=0;i<Nm;i++) {
minl[i+Nm]=i;
maxl[i+Nm]=i;
}
for (ll p=(Nm-1);p>=1;p--) {
minl[p]=minl[2*p];
maxl[p]=maxl[2*p];
}
}
void lft(ll p0) {
if (p0==0) {
return;
}
assert(lz[p0]==0);
//cout << "lz[p0="<<p0<<"]="<<lz[p0]<<"\n";
if (p0<Nm) {
if (minv[2*p0]<minv[2*p0+1]) {
minv[p0]=minv[2*p0];
minl[p0]=minl[2*p0];
} else {
minv[p0]=minv[2*p0+1];
minl[p0]=minl[2*p0+1];
}
if (maxv[2*p0]>maxv[2*p0+1]) {
maxv[p0]=maxv[2*p0];
maxl[p0]=maxl[2*p0];
} else {
maxv[p0]=maxv[2*p0+1];
maxl[p0]=maxl[2*p0+1];
}
}
}
void lftP(ll p0) {
for (ll e=1;e<=E;e++) {
if ((p0>>e)>0) {
//cout << "lifting at "<<(p0>>e) << "\n";
lft(p0>>e);
// if (1) {
// cout << "maxv="<<maxv[p0>>e]<<", maxl="<<maxl[p0>>e]<<"\n";
// cout << "minv="<<minv[p0>>e]<<", minl="<<minl[p0>>e]<<"\n";
// }
}
}
}
void pdn(ll p0) {
if (lz[p0]!=0) {
if (p0<Nm) {
lz[2*p0]+=lz[p0];
minv[2*p0]+=lz[p0];
maxv[2*p0]+=lz[p0];
lz[2*p0+1]+=lz[p0];
minv[2*p0+1]+=lz[p0];
maxv[2*p0+1]+=lz[p0];
}
lz[p0]=0;
}
}
void pdnP(ll p0) {
for (ll e=E;e>=0;e--) {
if (p0>>e) {
pdn(p0>>e);
}
}
}
void upd1(ll v0, ll p0) {
pdnP(p0);
lz[p0]+=v0;
minv[p0]+=v0;
maxv[p0]+=v0;
lftP(p0);
}
void upd0(ll v0, ll x0) {
if (x0>=Nm) {
return;
}
assert(x0<Nm);
ll vx = v2(Nm-x0);
upd1(v0,(1LL<<(E-vx))+(x0>>vx));
upd0(v0,x0+(1LL<<vx));
}
pii qrymax(ll a, ll b) { //{value, location}
if (a>b) {
return {-INF,-1};
}
ll va = v2(a); ll vb = v2(b+1);
if (va<vb) {
ll pc = (a>>va)+(1<<(E-va));
pdnP(pc);
//cout << "pc="<<pc<<"\n";
//cout << "max vals: "<<maxv[pc]<<","<<maxl[pc]<<"\n";
return fzmax({maxv[pc],maxl[pc]},qrymax(a+(1<<va),b));
} else {
ll pc = (b>>vb)+(1<<(E-vb));
pdnP(pc);
//cout << "pc="<<pc<<"\n";
//cout << "max vals: "<<maxv[pc]<<","<<maxl[pc]<<"\n";
return fzmax({maxv[pc],maxl[pc]},qrymax(a,b-(1<<vb)));
}
}
pii qrymin(ll a, ll b) {
if (a>b) {
return {INF,-1};
}
ll va = v2(a); ll vb = v2(b+1);
if (va<vb) {
ll pc = (a>>va)+(1<<(E-va));
pdnP(pc);
//cout << "pc="<<pc<<"\n";
//cout << "min vals: "<<minv[pc]<<","<<minl[pc]<<"\n";
return fzmin({minv[pc],minl[pc]},qrymin(a+(1<<va),b));
} else {
ll pc = (b>>vb)+(1<<(E-vb));
pdnP(pc);
//cout << "pc="<<pc<<"\n";
//cout << "min vals: "<<minv[pc]<<","<<minl[pc]<<"\n";
return fzmin({minv[pc],minl[pc]},qrymin(a,b-(1<<vb)));
}
}
ll qry0(ll c0) {
//cout << "querying c0="<<c0<<"\n";
ll xmin = -1; ll xmax = Nm-1;
while (xmin!=xmax) {
ll xtest = (xmin+xmax+1)/2;
//cout << "xtest="<<xtest<<"\n";
pii p1 = qrymin(xtest,Nm-1);
//cout << "p1="<<p1.first<<","<<p1.second<<"\n";
pii p2 = qrymax(xtest,Nm-1);
//cout << "p2="<<p2.first<<","<<p2.second<<"\n";
if (abs(p1.first-p2.first)>=c0) {
xmin = xtest;
} else {
xmax = xtest-1;
}
}
//cout << "xmin="<<xmin<<"\n";
if (xmin==-1) {
//return qrymax(Nm-1,Nm-1).first;
ll v1 = qrymin(0,Nm-1).first;
ll vf = qrymax(Nm-1,Nm-1).first;
return (vf-v1);
} else {
pii p1 = qrymin(xmin,Nm-1);
//cout << "p1="<<p1.first<<","<<p1.second<<"\n";
pii p2 = qrymax(xmin,Nm-1);
//cout << "p2="<<p2.first<<","<<p2.second<<"\n";
ll vf = qrymax(Nm-1,Nm-1).first;
//cout << "vf="<<vf<<"\n";
if (p1.second>p2.second) { //min comes last
return (vf-p1.first);
} else {
return (c0-p2.first+vf);
}
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
init();
ll N = c.size(); ll Q = l.size();
vector<pii> updV[N+1];
//store: {value to change by, starting index of update}
for (ll q=0;q<Q;q++) {
updV[l[q]].push_back({v[q],q+1});
updV[r[q]+1].push_back({-v[q],q+1});
}
vector<int> ans;
for (ll x=0;x<N;x++) {
for (pii p0: updV[x]) {
upd0(p0.first,p0.second);
}
ll ans1 = qry0(c[x]);
//cout << ans1 << "\n";
ans.push_back(ans1);
}
return ans;
}
