#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
os<<"{"<<p.ff<<", "<<p.ss<<"}";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
for (size_t i = 0; i < v.size(); ++i) {
if (i) os << ", ";
os << v[i];
}
os << "}";
return os;
}
ll fct[1000007];
ll fp(ll a,ll b){
ll c=1;while(b){if(b&1)c=(c*a)%MOD;a=(a*a)%MOD;b/=2;}
return c;
}
ll iv(ll a){
return fp(a,MOD-2);
}
ll bnm(ll a,ll b){
if(b>a || a<0)return 0;
return ((fct[a]*iv(fct[b]))%MOD*iv(fct[a-b]))%MOD;
}
ll mn[POT],mx[POT];
ll lz[POT];
void pusz(ll v){
mn[v*2]+=lz[v];
mx[v*2]+=lz[v];
lz[v*2]+=lz[v];
lz[v*2+1]+=lz[v];
mx[v*2+1]+=lz[v];
mn[v*2+1]+=lz[v];
lz[v]=0;
}
void pull(ll v){
mn[v]=min(mn[v*2],mn[v*2+1]);
mx[v]=max(mx[v*2],mx[v*2+1]);
}
void add(ll v,ll l,ll r,ll pocz,ll kon,ll x){
//cout<<v<<" "<<l<<" "<<r<<" "<<pocz<<" "<<kon<<"\n"<<flush;
if(l>kon || r<pocz)return;
if(l>=pocz && r<=kon){
mn[v]+=x;
mx[v]+=x;
lz[v]+=x;
return;
}
pusz(v);
add(v*2,l,(l+r)/2,pocz,kon,x);
add(v*2+1,(l+r)/2+1,r,pocz,kon,x);
pull(v);
}
ll gt(ll v){
v+=POT/2-1;
ll v2=v;
vi p;
v/=2;
while(v){
p.pb(v);v/=2;
}
while(p.size()){
pusz(p.back());
p.pop_back();
}
return mn[v2];
}
ll frt(ll v,ll l,ll r,ll x,ll mal,ll duz){
if(l==r)return l;
pusz(v);
// cout<<v<<" "<<l<<" "<<r<<" "<<x<<" "<<mal<<" "<<duz<<" "<<mn[v*2+1]<<" "<<mx[v*2+1]<<"\n";
if(max(duz,mx[v*2+1])-min(mal,mn[v*2+1])>=x)return frt(v*2+1,(l+r)/2+1,r,x,mal,duz);
return frt(v*2,l,(l+r)/2,x,min(mal,mn[v*2+1]),max(duz,mx[v*2+1]));
}
ll mnn(ll v,ll pocz,ll kon,ll l,ll r){
if(l>kon || r<pocz)return INFL;
if(l>=pocz && r<=kon)return mn[v];
pusz(v);
return min(mnn(v*2,pocz,kon,l,(l+r)/2),mnn(v*2+1,pocz,kon,(l+r)/2+1,r));
}
ll mxx(ll v,ll pocz,ll kon,ll l,ll r){
if(l>kon || r<pocz)return -INFL;
if(l>=pocz && r<=kon)return mx[v];
pusz(v);
return max(mxx(v*2,pocz,kon,l,(l+r)/2),mxx(v*2+1,pocz,kon,(l+r)/2+1,r));
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v){
ll n=c.size();
l.insert(l.begin(),0);
r.insert(r.begin(),n-1);
v.insert(v.begin(),-INF);
ll q=l.size();
ll sm=0;
vii op[n+1];
for(ll i=0;i<q;i++){
op[l[i]].pb({i,v[i]});
op[r[i]+1].pb({i,-v[i]});
}
vector<int>ans;
for(ll i=0;i<n;i++){
for(auto j : op[i]){
add(1,1,POT/2,j.ff+1,POT/2,j.ss);
sm+=j.ss;
}
ll x=frt(1,1,POT/2,c[i],INFL,-INFL);
ll du=mxx(1,x,POT/2,1,POT/2);
ll ma=mnn(1,x,POT/2,1,POT/2);
if(du-gt(x)>=c[i]){
ans.pb(c[i]-du+sm);
}
else{
ans.pb(sm-ma);
}
}
return ans;
}
