#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)(1e18);
const int N = 210000;
int n, q;
struct segtree {
struct node {
ll mn, mnpos, mx, mxpos, lz;
node() {mn = INF; mx = -INF;}
};
vector<node> vv;
int n;
segtree(int n) {
this->n = n;
vv = vector<node>(4 * (n + 1) + 1);
build(1, 0, n);
}
void build(int v, int l, int r) {
vv[v].mn = vv[v].mx = vv[v].lz = 0;
vv[v].mnpos = vv[v].mxpos = r;
if (l == r) return;
int mid = (l + r) / 2;
build(v * 2 + 0, l, mid);
build(v * 2 + 1, mid + 1, r);
}
void push(int v, int l, int r) {
if (vv[v].lz == 0) return;
vv[v].mn += vv[v].lz;
vv[v].mx += vv[v].lz;
if (l != r) {
vv[v * 2 + 0].lz += vv[v].lz;
vv[v * 2 + 1].lz += vv[v].lz;
}
vv[v].lz = 0;
}
node merge(node a, node b) {
node res;
res.mn = min(a.mn, b.mn);
res.mx = max(a.mx, b.mx);
if (b.mn <= a.mn) res.mnpos = b.mnpos;
else res.mnpos = a.mnpos;
if (b.mx >= a.mx) res.mxpos = b.mxpos;
else res.mxpos = a.mxpos;
return res;
}
void add(int v, int l, int r, int ql, int qr, int k) {
push(v, l, r);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
vv[v].lz += k;
push(v, l, r);
return;
}
int mid = (l + r) / 2;
add(v * 2 + 0, l, mid, ql, qr, k);
add(v * 2 + 1, mid + 1, r, ql, qr, k);
vv[v] = merge(vv[v * 2 + 0], vv[v * 2 + 1]);
}
node getnode(int v, int l, int r, int ql, int qr) {
push(v, l, r);
if (qr < l || r < ql) return node();
if (ql <= l && r <= qr) return vv[v];
int mid = (l + r) / 2;
return merge(getnode(v * 2 + 0, l, mid, ql, qr), getnode(v * 2 + 1, mid + 1, r, ql, qr));
}
ll getval(int v, int l, int r, int k) {
push(v, l, r);
if (l == r) return vv[v].mn;
int mid = (l + r) / 2;
if (k <= mid)
return getval(v * 2 + 0, l, mid, k);
return getval(v * 2 + 1, mid + 1, r, k);
}
ll smx, smn;
int getpos(int v, int l, int r, int c) {
push(v, l, r);
ll cmx = max(vv[v].mx, smx);
ll cmn = min(vv[v].mn, smn);
if (cmx - cmn <= c) {
smx = cmx;
smn = cmn;
return -1;
}
if (l == r) return l;
int mid = (l + r) / 2;
int ans = getpos(v * 2 + 1, mid + 1, r, c);
if (ans != -1) return ans;
return getpos(v * 2 + 0, l, mid, c);
}
void add(int ql, int qr, int k) {
add(1, 0, n, ql, qr, k);
}
int getmin(int l, int r) {
node tt = getnode(1, 0, n, l, r);
return tt.mnpos;
}
int getmax(int l, int r) {
node tt = getnode(1, 0, n, l, r);
return tt.mxpos;
}
ll getval(int k) {
return getval(1, 0, n, k);
}
int getpos(int c) {
smx = -INF;
smn = INF;
return getpos(1, 0, n, c);
}
};
vector<array<int, 2>> vv[N];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size();
q = l.size();
for (int i = 0; i < q; i++) {
l[i]++; r[i]++;
vv[l[i]].push_back({i + 1, v[i]});
vv[r[i] + 1].push_back({i + 1, -v[i]});
}
segtree seg(q);
vector<int> ans;
for (int i = 1; i <= n; i++) {
for (auto [k, v] : vv[i])
seg.add(k, q, v);
int C = c[i - 1];
int pos = seg.getpos(C);
if (pos == -1) {
int k = seg.getmin(0, q);
ans.push_back(seg.getval(q) - seg.getval(k));
} else {
int mn = seg.getmin(pos, q);
int mx = seg.getmax(pos, q);
if (mn > mx)
ans.push_back(seg.getval(q) - seg.getval(mn));
else
ans.push_back(seg.getval(q) - seg.getval(mx) + C);
}
}
return ans;
}
/*
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> c(n);
for(int i = 0; i < n; ++i) {
assert(scanf("%d", &c[i]) == 1);
}
int q;
assert(1 == scanf("%d", &q));
std::vector<int> l(q), r(q), v(q);
for(int i = 0; i < q; ++i) {
assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
}
std::vector<int> ans = distribute_candies(c, l, r, v);
for(int i = 0; i < n; ++i) {
if (i > 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
fclose(stdout);
return 0;
}
//*/
