/*************************************
* author: marvinthang *
* created: 15.10.2022 08:23:32 *
*************************************/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define div ___div
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define FULL(i) (MASK(i) - 1)
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T> print_op(vector <T>) { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V> scan_op(pair <U, V>) { return in >> u.fi >> u.se; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.fi << ", " << u.se << ')'; }
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const long long oo = 1e18;
struct Node {
long long mi, ma, lazy;
Node(): mi(oo), ma(-oo), lazy(0) {}
Node(long long a, long long b, long long c): ma(a), mi(b), lazy(c) {}
Node operator + (const Node &other) const {
return Node(max(ma, other.ma), min(mi, other.mi), 0);
}
};
struct SegmentTree {
int n;
vector <Node> st;
void add(int i, long long val) {
st[i].ma += val;
st[i].mi += val;
st[i].lazy += val;
}
SegmentTree(int n = 0): n(n), st(n << 2, Node(0, 0, 0)) {}
void pushDown(int i) {
if (!st[i].lazy) return;
add(i << 1, st[i].lazy);
add(i << 1 | 1, st[i].lazy);
st[i].lazy = 0;
return;
}
void update(int i, int l, int r, int u, int v, long long val) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
add(i, val);
return;
}
pushDown(i);
int m = l + r >> 1;
update(i << 1, l, m, u, v, val);
update(i << 1 | 1, m + 1, r, u, v, val);
st[i] = st[i << 1] + st[i << 1 | 1];
}
void update(int l, int r, long long val) { update(1, 0, n, l, r, val); }
Node get(int i, int l, int r, int u, int v) {
if (l > v || r < u) return Node();
if (u <= l && r <= v) return st[i];
int m = l + r >> 1;
pushDown(i);
return get(i << 1, l, m, u, v) + get(i << 1 | 1, m + 1, r, u, v);
}
Node get(int l, int r) { return get(1, 0, n, l, r); }
};
vector <int> distribute_candies(vector <int> c, vector <int> ql, vector <int> qr, vector <int> qv) {
int n = c.size(), q = ql.size();
vector <vector <pair <int, int>>> events(n + 1);
for (int i = 0; i < q; ++i) {
events[ql[i]].push_back(make_pair(i, qv[i]));
events[qr[i] + 1].push_back(make_pair(i, -qv[i]));
}
vector <int> res(n);
SegmentTree st(q);
for (int i = 0; i < n; ++i) {
for (auto [p, v]: events[i]) st.update(p + 1, q, v);
int l = 0, r = q;
while (l <= r) {
int m = l + r >> 1;
Node cc = st.get(m, q);
if (cc.ma - cc.mi > c[i]) l = m + 1;
else r = m - 1;
}
if (r == -1) res[i] = st.get(q, q).ma - st.get(0, q).mi;
else {
if (st.get(r, r).ma == st.get(r, q).mi) res[i] = c[i] - (st.get(r, q).ma - st.get(q, q).ma);
else res[i] = st.get(q, q).mi - st.get(r, q).mi;
}
}
return res;
}
