#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
#define lpos pos*2
#define rpos pos*2+1
const ll INF = 1e18;
const int SIZE = 2e5 + 5;
int n, q;
vector<pair<int, int>> op[SIZE];
struct Node {
ll mn, mx, lazy;
Node() = default;
Node operator + (const Node& r) const {
Node re = Node();
re.mn = min(mn, r.mn);
re.mx = max(mx, r.mx);
return re;
}
} node[SIZE * 4];
void push(int pos, int l, int r) {
node[pos].mn += node[pos].lazy;
node[pos].mx += node[pos].lazy;
if (l < r) {
node[lpos].lazy += node[pos].lazy;
node[rpos].lazy += node[pos].lazy;
}
node[pos].lazy = 0;
}
void pull(int pos, int l, int r) {
int mid = (l + r) / 2;
push(lpos, l, mid);
push(rpos, mid + 1, r);
node[pos] = node[lpos] + node[rpos];
}
void upd(int pos, int l, int r, int L, int R, int x) {
if (l == L && r == R) {
node[pos].lazy += x;
return;
}
push(pos, L, R);
int mid = (L + R) / 2;
if (r <= mid) upd(lpos, l, r, L, mid, x);
else if (l > mid) upd(rpos, l, r, mid + 1, R, x);
else {
upd(lpos, l, mid, L, mid, x);
upd(rpos, mid + 1, r, mid + 1, R, x);
}
pull(pos, L, R);
}
void upd(int p, int x) {
upd(1, p, q, 0, q, x);
}
ll que(int pos, int l, int r, int p) {
push(pos, l, r);
if (l == r) return node[pos].mn;
int mid = (l + r) / 2;
if (p <= mid) return que(lpos, l, mid, p);
else return que(rpos, mid + 1, r, p);
}
ll que(int l, int r) {
return que(1, 0, q, r) - (l ? que(1, 0, q, l - 1) : 0);
}
ll que(int pos, int l, int r, int L, int R, int ty) {
push(pos, L, R);
if (l == L && r == R) return (ty == 0 ? node[pos].mn : node[pos].mx);
int mid = (L + R) / 2;
if (r <= mid) return que(lpos, l, r, L, mid, ty);
if (l > mid) return que(rpos, l, r, mid + 1, R, ty);
ll lval = que(lpos, l, mid, L, mid, ty);
ll rval = que(rpos, mid + 1, r, mid + 1, R, ty);
return ty == 0 ? min(lval, rval) : max(lval, rval);
}
int sch_mn(int pos, int l, int r) {
if (l == r) return l;
int mid = (l + r) / 2;
push(pos, l, r);
push(rpos, mid + 1, r);
if (node[rpos].mn == node[pos].mn) return sch_mn(rpos, mid + 1, r);
else return sch_mn(lpos, l, mid);
}
int sch_mn() {
return sch_mn(1, 0, q);
}
tuple<int, ll, ll> sch_rdif(int pos, int l, int r, int lim, ll pmn = INF, ll pmx = -INF) {
push(pos, l, r);
if (l == r) {
pmn = min(pmn, node[pos].mn);
pmx = max(pmx, node[pos].mx);
return {l, pmn, pmx};
}
int mid = (l + r) / 2;
push(rpos, mid + 1, r);
ll rmn = min(pmn, node[rpos].mn);
ll rmx = max(pmx, node[rpos].mx);
if (rmx - rmn >= lim) return sch_rdif(rpos, mid + 1, r, lim, pmn, pmx);
else return sch_rdif(lpos, l, mid, lim, rmn, rmx);
}
pair<int, int> sch_rdif(int lim) {
auto [lp, mn, mx] = sch_rdif(1, 0, q, lim);
return {lp, que(0, lp) != mn};
}
int sch(int pos, int l, int r, int L, int R, int ty, ll x, ll pval) {
push(pos, L, R);
if (l == L && r == R) {
if (l == r) return l;
int mid = (L + R) / 2;
push(rpos, mid + 1, R);
ll rval = (ty == 0 ? min(node[rpos].mn, pval) : max(node[rpos].mx, pval));
if (rval == x) return sch(rpos, mid + 1, r, mid + 1, R, ty, x, pval);
else return sch(lpos, l, mid, L, mid, ty, x, rval);
}
int mid = (L + R) / 2;
if (l > mid) return sch(rpos, l, r, mid + 1, R, ty, x, pval);
push(rpos, mid + 1, R);
ll rval = (ty == 0 ? min(node[rpos].mn, pval) : max(node[rpos].mx, pval));
if (rval == x) return sch(rpos, mid + 1, r, mid + 1, R, ty, x, pval);
else return sch(lpos, l, mid, L, mid, ty, x, rval);
}
int sch(int l, int r, int ty) {
ll x = que(1, l, r, 0, q, ty);
return sch(1, l, r, 0, q, ty, x, (ty == 0 ? INF : -INF));
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size(), q = l.size();
FOR (i, 0, q - 1) {
op[l[i]].pb(i + 1, v[i]);
op[r[i] + 1].pb(i + 1, -v[i]);
}
vector<int> ans(n);
FOR (i, 0, n - 1) {
for (auto [p, x] : op[i]) upd(p, x);
if (node[1].mx - node[1].mn <= c[i]) {
int lp = sch_mn();
ans[i] = que(lp + 1, q);
continue;
}
auto [lp, ty] = sch_rdif(c[i]);
int rp = sch(lp + 1, q, !ty);
ans[i] = (ty == 0 ? c[i] : 0) + que(rp + 1, q);
}
return ans;
}
