#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define sz(v) ((int)v.size())
#define pb push_back
#define pry cout << "YES\n"
#define prn cout << "NO\n"
#define endl '\n'
#define fst first
#define scn second
/* #define ONPC */
using vi = vector<int>;
using vl = vector<long long>;
using pl = pair<ll,ll>;
struct aint{
int n;
vector<pl> mn, mx;
vl lenes;
vl sum;
vi mid;
aint(int _n)
: n(_n)
{
mn.assign(4*n,{inf,0});
mx.assign(4*n,{-inf,0});
mid.assign(4*n, 0);
sum.assign(4*n, 0);
lenes.assign(4*n,0);
build(1, 0, n-1);
}
/* TODO */
/* build */
void
build(int i, int l, int r)
{
mid[i] = (l+r)>>1;
mn[i].scn = r;
mn[i].fst = 0;
mx[i].scn = r;
mx[i].fst = 0;
if (l == r) return;
build(i<<1, l, mid[i]);
build(i<<1|1, mid[i]+1, r);
}
pl
querymn(int i, int l, int r, int tl, int tr, ll ex)
{
ex += lenes[i];
if (tr < l || r < tl) return {inf, 0};
if (tl <= l && r <= tr) return {mn[i].fst+ex, mn[i].scn};
auto lf = querymn(i<<1, l, mid[i], tl, tr, ex);
auto rt = querymn(i<<1|1, mid[i]+1, r, tl, tr, ex);
if (lf.fst < rt.fst) return lf;
return rt;
}
pl
querymx(int i, int l, int r, int tl, int tr, ll ex)
{
ex += lenes[i];
if (tr < l || r < tl) return {-inf, 0};
if (tl <= l && r <= tr) return {mx[i].fst+ex, mx[i].scn};
auto lf = querymx(i<<1, l, mid[i], tl, tr, ex);
auto rt = querymx(i<<1|1, mid[i]+1, r, tl, tr, ex);
if (lf.fst > rt.fst) return lf;
return rt;
}
void
lenesupd(int i, int l, int r, int tl, int tr, int v)
{
if (tr < l || r < tl) return;
if (tl <= l && r <= tr) {
lenes[i] += v;
return;
}
lenesupd(i<<1, l, mid[i], tl, tr, v);
lenesupd(i<<1|1, mid[i]+1, r, tl, tr, v);
int ind;
if (mn[i<<1].fst+lenes[i<<1] < mn[i<<1|1].fst + lenes[i<<1|1])
ind = i<<1;
else
ind = i<<1|1;
mn[i] = {mn[ind].fst+lenes[ind], mn[ind].scn};
if (mx[i<<1].fst+lenes[i<<1] > mx[i<<1|1].fst + lenes[i<<1|1])
ind = i<<1;
else
ind = i<<1|1;
mx[i] = {mx[ind].fst+lenes[ind], mx[ind].scn};
}
void
updsum(int i, int l, int r, int x, int v)
{
if (x < l || r < x) return;
sum[i] += v;
if (l == r) return;
updsum(i<<1, l, mid[i], x, v);
updsum(i<<1|1, mid[i]+1, r, x, v);
}
void
upd(int x, int v)
{
lenesupd(1, 0, n-1, x, n-1, v);
updsum(1, 0, n-1, x, v);
return;
}
ll
qsum(int i, int l, int r, int tl, int tr)
{
if (tr < l || r < tl) return 0;
if (tl <= l && r <= tr) return sum[i];
return
qsum(i<<1, l, mid[i], tl, tr) +
qsum(i<<1|1, mid[i]+1, r, tl, tr);
}
/* User functions */
pl querymn(int l, int r) { return querymn(1, 0, n-1, l, r, 0); }
pl querymx(int l, int r) { return querymx(1, 0, n-1, l, r, 0); }
ll qsum(int x) { return qsum(1, 0, n-1, x, n-1); }
pl
query(int x, int& ismx)
{
auto mx = querymx(x, n-1);
auto mn = querymn(x, n-1);
ismx = (mx.scn > mn.scn) ? 1 : 0;
return {mx.fst - mn.fst, max(mx.scn, mn.scn)};
}
};
vi
distribute_candies(vi c, vi l, vi r, vi v)
{
int n = sz(c);
int q = sz(l);
vi ans;
aint tr(q+1);
vector<array<int,2>> qin, qout;
for (int i = 0; i < q; ++i) {
qin.pb({l[i],i});
qout.pb({r[i],i});
}
sort(qin.begin(), qin.end());
sort(qout.begin(), qout.end());
int pin = 0;
int pout = 0;
for (int i = 0; i < n; ++i) {
while (pin < q) {
if (qin[pin][0] > i) break;
tr.upd(qin[pin][1]+1, v[qin[pin][1]]);
++pin;
}
/* Find valid */
int sp = tr.querymn(0, q).scn;
ll a;
if (sp == q) {
ans.pb(0);
continue;
}
/* cout << sp << endl; */
int ismx, tismx;
ismx = 0;
int sump = sp;
int l, r, mid;
l = sp;
r = q+1;
while (l < r) {
int mid = (l+r)>>1;
auto qr = tr.query(mid,tismx);
if (qr.fst > c[i]) {
l = mid+1;
if (qr.scn > sump) {
sump = qr.scn;
ismx = tismx;
}
} else {
r = mid;
}
}
if (ismx)
a = c[i];
else
a = 0;
if (sump < q)
a += tr.qsum(sump+1);
a = max(a,0ll);
a = min(a,(ll)c[i]);
ans.pb(a);
while (pout < q) {
if (qout[pout][0] > i) break;
tr.upd(qout[pout][1]+1, -v[qout[pout][1]]);
++pout;
}
}
return ans;
}
#ifdef ONPC
void
solve()
{
int n, q;
cin >> n >> q;
vector<int> c(n);
for (int i = 0; i < n; ++i)
cin >> c[i];
vector<int> l(q), r(q), v(q);
for (int i = 0; i < q; ++i)
cin >> l[i] >> r[i] >> v[i];
vi ans = distribute_candies(c,l,r,v);
for (int i = 0; i < sz(ans); ++i) {
cout << ans[i] << ' ';
}
cout << endl;
}
int32_t
main(int argc, char **argv)
{
if (argc >= 2) {
freopen(argv[1], "r", stdin);
} else
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
