/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
using ll = long long;
using ull = int64_t;
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
//#define ll long long
const char nl = '\n';
const ll N = 2e5+1;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll mod = 1e9+7;
struct node {
ll mx, mn, mni, mxi, lz;
node () {
mx = -inf, mn = inf, mni = 0, mxi = 0, lz = 0;
}
};
struct segtree {
vector<node> tree;
ll size;
void init(ll n) {
size = 1;
while (size < n)size<<=1;
tree.assign(2*size-1, node());
}
void build(ll x, ll lx, ll rx) {
tree[x].mx = tree[x].mn = 0;
tree[x].mni = tree[x].mxi = lx;
tree[x].lz = 0;
if (rx-lx==1)return;
ll mid = lx+rx>>1;
build(2*x+1, lx, mid);
build(2*x+2, mid, rx);
tree[x] = comb(tree[2*x+1], tree[2*x+2]);
}
void build(ll n) {
init(n);
build(0, 0, size);
}
void addval(ll x, ll v) {
tree[x].mn += v, tree[x].mx += v;
tree[x].lz += v;
}
void push(ll x) {
tree[2*x+1].mn += tree[x].lz;
tree[2*x+1].mx += tree[x].lz;
tree[2*x+2].mn += tree[x].lz;
tree[2*x+2].mx += tree[x].lz;
tree[2*x+1].lz += tree[x].lz;
tree[2*x+2].lz += tree[x].lz;
tree[x].lz = 0;
}
node comb(node a, node b) {
node c;
if (a.mx > b.mx)c.mx = a.mx, c.mxi = a.mxi;
else c.mx = b.mx, c.mxi = b.mxi;
if (a.mn < b.mn)c.mn = a.mn, c.mni = a.mni;
else c.mn = b.mn, c.mni = b.mni;
c.lz = 0;
//c.lz = a.lz+b.lz;
return c;
}
void add(ll l, ll r, ll v, ll x, ll lx, ll rx) {
if (rx <= l || r <= lx)return;
if (lx >= l && rx <= r) {
addval(x, v);
return;
}
push(x);
ll mid = lx+rx>>1;
add(l, r, v, 2*x+1, lx, mid);
add(l, r, v, 2*x+2, mid, rx);
tree[x] = comb(tree[2*x+1], tree[2*x+2]);
}
void add(ll l, ll r, ll v) {
add(l, r, v, 0, 0, size);
}
node get(ll l, ll r, ll x, ll lx, ll rx) {
if (rx <= l || r <= lx)return node();
if (lx >= l && rx <= r)return tree[x];
ll mid = lx+rx>>1;
push(x);
return comb(get(l, r, 2*x+1, lx, mid), get(l, r, 2*x+2, mid, rx));
tree[x] = comb(tree[2*x+1], tree[2*x+2]);
}
node get(ll l, ll r) {
return get(l, r, 0, 0, size);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int>r, vector<int> v) {
segtree st; st.build(sz(l)+1);
ll n = sz(c), q = sz(l);
vector<pair<ll, ll>> g[n+1];
for (ll i = 0; i < q; ++i) {
g[l[i]].push_back(make_pair(i, v[i]));
if (r[i] < n-1)g[r[i]+1].push_back(make_pair(i, -v[i]));
}
vector<int> res(n);
ll sum = 0;
for (ll i = 0; i < n; ++i) {
for (auto j: g[i]) {
st.add(j.first, q, j.second);
sum += j.second;
}
ll id = -1, wall = -1, tp = 0;
ll lx = 0, rx = q-1;
while (lx <= rx) {
ll mid = lx+rx>>1;
node gt = st.get(mid, q);
if (gt.mx-gt.mn > c[i]) {
lx = mid+1;
if (gt.mni < gt.mxi)id = gt.mxi, wall = gt.mx, tp = 1;
else id = gt.mni, wall = gt.mn, tp = 0;
} else rx = mid-1;
}
if (id == -1) {
wall = 0;
node gt = st.get(0, q);
if (gt.mn < 0)wall = gt.mn;
if (gt.mx > 0 && gt.mx >= c[i])wall = gt.mx-c[i];
res[i] = sum-wall;
continue;
}
res[i] = (tp==0?sum-wall:sum-wall+c[i]);
}
return res;
}
void solve() {
ll n, q;
cin >> n;
vector<int> c(n);
for (auto &i : c) cin >> i;
cin >> q;
vector<int> l(q), r(q), v(q);
for (int i = 0; i < q; ++i)cin >> l[i] >> r[i] >> v[i];
vector<int> result = distribute_candies(c, l, r, v);
for (const auto &i : result) cout << i << " ";
}
//int main() {
//ios::sync_with_stdio(0), cin.tie(0);
//solve();
//}
