// Hello this is Tyx2019's clone
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define debug(x) cerr << #x << " is " << x << "\n"
#define hehe ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repb(i, a, b) for (int i = b; i >= a; i--)
#define pii pair<int, int>
#define linebreak cout << "---------------------------------------------------------\n"
#define f first
#define s second
#define pb push_back
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// good luck
const long long MS = 2e5+5, mod = 1e9+9, INF = 3e18, blk = 400;
long long n, q;
struct node {
long long S, E;
long long lazy = 0, macs = 0, ming = 0;
node *left = NULL, *right = NULL;
node (long long s, long long e) {
S = s;
E = e;
macs = ming = 0;
}
void create() {
long long M = (S+E)>>1;
if (S != E) {
left = new node(S, M);
right = new node(M+1, E);
}
}
void propagate() {
if (left == NULL or right == NULL) create();
if (lazy == 0) return;
macs += lazy; ming += lazy;
if (S != E) {
left -> lazy += lazy;
right -> lazy += lazy;
}
lazy = 0;
}
void update(long long us, long long ue, long long v) {
long long M = (S+E)>>1;
propagate();
if (S == us and E == ue) {
lazy += v;
return;
}
if (ue <= M) left -> update(us, ue, v);
else if (us >= M+1) right -> update(us, ue, v);
else {
left -> update(us, M, v);
right -> update(M+1, ue, v);
}
left -> propagate();
right -> propagate();
macs = max(left -> macs, right -> macs);
ming = min(left -> ming, right -> ming);
}
pair<long long, pair<long long, long long>> bs(long long x, long long omacs, long long oming) {
if (S == E) return {S, {omacs, oming}};
propagate();
long long nmacs = max(omacs, right -> macs), nming = min(oming, right -> ming);
if (nmacs-nming <= x) {
return left -> bs(x, nmacs, nming);
}
else {
return right -> bs(x, omacs, oming);
}
}
long long query(long long x) {
if (S == E) return ming;
long long M = (S+E)>>1;
propagate();
if (x <= M) return left -> query(x);
return right -> query(x);
}
} *root;
vector<long long> L[MS], R[MS];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
vector<int> ans;
n = c.size(), q = v.size();
for (long long i = 0; i < q; i++) {
L[l[i]].pb(i); R[r[i]].pb(i);
}
root = new node(-2, q-1);
root -> update(-2, -2, INF);
for (long long i = 0; i < n; i++) {
for (auto it : L[i]) root -> update(it, q-1, v[it]);
long long endval = root -> query(q-1);
// process query for i
pair<long long, pair<long long, long long>> temp = root -> bs(c[i], -INF, INF);
if (root -> query(temp.f) > temp.s.f) ans.pb(endval-temp.s.s);
else ans.pb(c[i]-temp.s.f+endval);
for (auto it : R[i]) root -> update(it, q-1, -v[it]);
}
return ans;
}
