#include <iostream>
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef pair<int,int>pp;
typedef long long ll;
const int MAXN=200000;
int n,q;
ll sum,maxs[1<<19],mins[1<<19],lazy[1<<19];
vector<pp>query[MAXN];
void update(int a,int b,int c,int be,int en,int v){
if(lazy[c]!=0){
maxs[c]+=lazy[c];
mins[c]+=lazy[c];
if(a!=b){
lazy[2*c+1]+=lazy[c];
lazy[2*c+2]+=lazy[c];
}
lazy[c]=0;
}
if(a>b||a>en||b<be)return;
if(a>=be&&b<=en){
maxs[c]+=v;
mins[c]+=v;
if(a!=b){
lazy[2*c+1]+=v;
lazy[2*c+2]+=v;
}
return;
}
update(a,(a+b)/2,2*c+1,be,en,v);
update((a+b)/2+1,b,2*c+2,be,en,v);
maxs[c]=max(maxs[2*c+1],maxs[2*c+2]);
mins[c]=min(mins[2*c+1],mins[2*c+2]);
}
ll maxq(int a,int b,int c,int be,int en){
if(lazy[c]!=0){
maxs[c]+=lazy[c];
mins[c]+=lazy[c];
if(a!=b){
lazy[2*c+1]+=lazy[c];
lazy[2*c+2]+=lazy[c];
}
lazy[c]=0;
}
if(a>b||a>en||b<be)return LLONG_MIN;
if(a>=be&&b<=en)return maxs[c];
return max(maxq(a,(a+b)/2,2*c+1,be,en),maxq((a+b)/2+1,b,2*c+2,be,en));
}
ll minq(int a,int b,int c,int be,int en){
if(lazy[c]!=0){
maxs[c]+=lazy[c];
mins[c]+=lazy[c];
if(a!=b){
lazy[2*c+1]+=lazy[c];
lazy[2*c+2]+=lazy[c];
}
lazy[c]=0;
}
if(a>b||a>en||b<be)return LLONG_MAX;
if(a>=be&&b<=en)return mins[c];
return min(minq(a,(a+b)/2,2*c+1,be,en),minq((a+b)/2+1,b,2*c+2,be,en));
}
ll range(int p){
return maxq(0,q-1,0,p,q-1)-minq(0,q-1,0,p,q-1);
}
ll edge(int s){
ll mx=maxq(0,q-1,0,0,q-1);
if(mx>s)return mx-s;
ll mn=minq(0,q-1,0,0,q-1);
if(mn<0)return mn;
else return 0;
}
ll norm(int p,int s){
ll mx=maxq(0,q-1,0,p,q-1);
ll mn=minq(0,q-1,0,p,q-1);
if(maxq(0,q-1,0,p-1,q-1)>mx)return mn;
else if(minq(0,q-1,0,p-1,q-1)<mn)return mx-s;
}
int calc(int s){
int lef=0;
int rig=q-1;
int mid=(lef+rig)/2;
while(rig-lef>1){
if(range(mid)>s)lef=mid;
else rig=mid;
mid=(lef+rig)/2;
}
if(range(lef)<=s)mid=lef;
else mid=rig;
ll lb=0;
if(mid==0)lb=edge(s);
else lb=norm(mid,s);
return sum-lb;
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v){
vector<int>ret;
n=c.size();
q=v.size();
for(int i=0;i<q;i++){
query[l[i]].push_back({i,v[i]});
if(r[i]!=n-1)query[r[i]+1].push_back({i,-v[i]});
}
sum=0;
memset(maxs,0,sizeof(maxs));
memset(mins,0,sizeof(mins));
memset(lazy,0,sizeof(lazy));
for(int i=0;i<n;i++){
for(pp j:query[i]){
sum+=j.second;
update(0,q-1,0,j.first,q-1,j.second);
}
ret.push_back(calc(c[i]));
}
return ret;
}
