#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN = 2e5+5;
int n, q;
ll mx[MXN<<2], mn[MXN<<2], lz[MXN<<2];
inline void apply(ll x, int id) {
mx[id] += x;
mn[id] += x;
lz[id] += x;
}
inline void push(int id) {
if(lz[id]) {
apply(lz[id], lc);
apply(lz[id], rc);
lz[id] = 0;
}
}
void upd(int s, int e, ll x, int l=0, int r=q+1, int id=1) {
if(s>=r || l>=e) return;
if(s<=l && r<=e) {
apply(x, id);
return;
}
push(id);
upd(s, e, x, l, mid, lc);
upd(s, e, x, mid, r, rc);
mx[id] = max(mx[lc], mx[rc]);
mn[id] = min(mn[lc], mn[rc]);
}
ll cmx_, cmn_, val;
int find(ll lb, ll cmx=-1e18, ll cmn=1e18, int l=0, int r=q+1, int id=1) {
if(max(mx[id], cmx)-min(mn[id], cmn)<lb) return -1;
if(r-l == 1) { cmx_=max(cmx, mx[id]), cmn_=min(cmn, mn[id]), val=mx[id]; return l; }
push(id);
int res = find(lb, cmx, cmn, mid, r, rc);
return res==-1 ? find(lb, max(cmx, mx[rc]), min(cmn, mn[rc]), l, mid, lc) : res;
}
vector<int> S[MXN], E[MXN];
vector<int> distribute_candies(vector<int> c, vector<int> lq, vector<int> rq, vector<int> vq) {
n = c.size(), q = lq.size();
for(int i=0; i<q; i++) {
S[lq[i]].push_back(i);
E[rq[i]+1].push_back(i);
}
ll tot = 0;
vector<int> ans(n);
for(int i=0; i<n; i++) {
for(int j : S[i]) tot += vq[j], upd(j+1, q+1, vq[j]);
for(int j : E[i]) tot -= vq[j], upd(j+1, q+1, -vq[j]);
int wh = find(c[i]);
if(wh==-1) ans[i] = tot-mn[1];
else ans[i] = val==cmx_ ? tot-cmn_ : tot-cmx_+c[i];
}
return ans;
}
