/**
* 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;
int size;
void init(int n) {
size = 1;
while (size < n)size<<=1;
tree.assign(2*size-1, node());
}
void build(int x, int lx, int rx) {
tree[x].mx = tree[x].mn = 0;
tree[x].mni = tree[x].mxi = lx;
tree[x].lz = 0;
if (rx-lx==1)return;
int mid = lx+rx>>1;
build(2*x+1, lx, mid);
build(2*x+2, mid, rx);
}
void build(int n) {
init(n);
build(0, 0, size);
}
void addval(int x, int v) {
tree[x].mn += v, tree[x].mx += v;
tree[x].lz += v;
}
void push(int x) {
tree[2*x+1].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;
return c;
}
void add(int l, int r, int v, int x, int lx, int rx) {
if (rx <= l || r <= lx)return;
if (lx >= l && rx <= r) {
addval(x, v);
return;
}
push(x);
int 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(int l, int r, int v) {
add(l, r, v, 0, 0, size);
}
node get(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx)return node();
if (lx >= l && rx <= r)return tree[x];
int mid = lx+rx>>1;
return comb(get(l, r, 2*x+1, lx, mid), get(l, r, 2*x+2, mid, rx));
}
node get(int l, int 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);
int n = sz(c), q = sz(l);
vector<pair<int, int>> g[n+1];
for (int 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);
int sum = 0;
for (int 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;
int lx = 0, rx = q-1;
while (lx <= rx) {
int 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.mni, wall = gt.mn;
else id = gt.mxi, wall = gt.mx, tp = 1;
} else rx = mid-1;
}
//cout << sum << nl;
if (id == -1) {
node gt = st.get(0, q);
cout << gt.mn << " " << gt.mx << nl;
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() {
int n, q;
cin >> n >> q;
vector<int> c(n), l(q), r(q), v(q);
for (auto &i : c) cin >> i;
for (auto &i : l) cin >> i;
for (auto &i : r) cin >> i;
for (auto &i : v) cin >> i;
vector<int> result = distribute_candies(c, l, r, v);
for (const auto &i : result) cout << i << " ";
//int n;
//cin >> n;
//segtree T(n);
//while (1) {
//string op;
//int l, r, v;
//cin >> op;
//if (op == "add") {
//cin >> l >> v;
//T.add(l, v);
//}
//else if (op == "minimix") {
//cin >> l >> r;
//info res = T.minimix(l, r);
//printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
//}
//else if (op == "suffix") {
//cin >> v;
//info res = T.suffix(v);
//printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
//}
//}
}
//int main() {
//ios::sync_with_stdio(0), cin.tie(0);
//solve();
//}
