#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define dforn(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using vi = vector<int>;
using vb = vector<bool>;
using ii = pair<int, int>;
using ll = long long;
#define pb push_back
#define eb emplace_back
const int SZ = 1 << 18;
const ll INF = 1e18;
pair<ll, ll> st[2 * SZ];
ll lazy[2 * SZ];
int C;
#define fst first
#define snd second
void pass(int u) {
if (u < SZ) {
lazy[2 * u] += lazy[u];
lazy[2 * u + 1] += lazy[u];
}
st[u].fst += lazy[u];
st[u].snd += lazy[u];
lazy[u] = 0;
}
void update(int s, int e, int v, int l = 0, int r = SZ, int u = 1) {
pass(u);
if (e <= l || r <= s) return;
if (s <= l && r <= e) {
lazy[u] = v;
return pass(u);
}
int m = (l + r) / 2;
update(s, e, v, l, m, 2 * u);
update(s, e, v, m, r, 2 * u + 1);
st[u].fst = min(st[2 * u].fst, st[2 * u + 1].fst);
st[u].snd = max(st[2 * u].snd, st[2 * u + 1].snd);
}
ll queryMin(int s, int e, int l = 0, int r = SZ, int u = 1) {
pass(u);
if (e <= l || r <= s) return INF;
if (s <= l && r <= e) return st[u].fst;
int m = (l + r) / 2;
return min(queryMin(s, e, l, m, 2 * u), queryMin(s, e, m, r, 2 * u + 1));
}
ll queryMax(int s, int e, int l = 0, int r = SZ, int u = 1) {
pass(u);
if (e <= l || r <= s) return -INF;
if (s <= l && r <= e) return st[u].snd;
int m = (l + r) / 2;
return max(queryMax(s, e, l, m, 2 * u), queryMax(s, e, m, r, 2 * u + 1));
}
ll get(int p) { return queryMax(p, p + 1); }
int find(int c, int u, ll mini, ll maxi) {
while (u < SZ) {
u = 2 * u + 1;
pass(u);
if (max(st[u].snd, maxi) - min(st[u].fst, mini) < c) {
maxi = max(maxi, st[u].snd);
mini = min(mini, st[u].fst);
u--;
pass(u);
}
}
return u - SZ;
}
int find(int l, int r, int c) {
vi left, right;
for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
if (l & 1) left.pb(l++);
if (r & 1) right.pb(--r);
}
ll mini = INF, maxi = -INF;
vi nodes = right;
dforn(i, sz(left)) nodes.pb(left[i]);
for (int u : nodes) {
pass(u);
if (max(st[u].snd, maxi) - min(st[u].fst, mini) >= c) {
return find(c, u, mini, maxi);
}
maxi = max(maxi, st[u].snd);
mini = min(mini, st[u].fst);
}
return -1;
}
vi distribute_candies(vi c, vi l, vi r, vi v) {
int n = sz(c), q = sz(v);
vector<vector<ii>> add(n + 1), sub(n + 1);
forn(i, 2 * SZ) st[i].fst = INF, st[i].snd = -INF;
forsn(i, SZ, SZ + q + 1) st[i].fst = st[i].snd = 0;
dforsn(i, 1, SZ) {
st[i].fst = min(st[2 * i].fst, st[2 * i + 1].fst);
st[i].snd = max(st[2 * i].snd, st[2 * i + 1].snd);
}
forn(i, q) {
add[l[i]].eb(i, v[i]);
sub[r[i] + 1].eb(i, v[i]);
}
vi ret(n);
forn(i, n) {
for (auto [j, x] : add[i]) update(j + 1, q + 1, x);
for (auto [j, x] : sub[i]) update(j + 1, q + 1, -x);
int lo = find(0, q + 1, c[i]);
ll tot = get(q);
if (lo == -1) {
ret[i] = tot - queryMin(0, q + 1);
} else if (tot - get(lo) > 0) {
ll diff = tot - queryMax(lo, q + 1);
ret[i] = c[i] + diff;
} else {
ll diff = tot - queryMin(lo, q + 1);
ret[i] = diff;
}
}
return ret;
}
