#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 200 * 1000 + 10;
const ll INF = 1e18;
int n, q;
struct Node {
ll g, mi, mx;
};
Node T[(1 << 19)];
vi events[nax];
void prop(int v) {
T[2*v].g += T[v].g;
T[2*v + 1].g += T[v].g;
T[v].g = 0;
}
void add(int a, int b, int l, int r, int x, int v) {
if(a <= l && r <= b) {
T[v].g += x;
return;
}
prop(v);
int mid = (l + r) / 2;
if(a <= mid) add(a, b, l, mid, x, v * 2);
if(mid < b) add(a, b, mid + 1, r, x, v * 2 + 1);
T[v].mi = min(T[2*v].mi + T[2*v].g, T[2*v+1].mi + T[2*v+1].g);
T[v].mx = max(T[2*v].mx + T[2*v].g, T[2*v+1].mx + T[2*v+1].g);
}
tuple<int,ll,ll> ask(int d) {
int v = 1, l = 0, r = q - 1;
ll mi = INF, mx = -INF;
while(l < r) {
T[v].mi += T[v].g;
T[v].mx += T[v].g;
prop(v);
//cout << l << " " << r << "\n";
int mid = (l + r) / 2;
if(max(mx, T[2 * v + 1].mx + T[2*v+1].g) - min(mi, T[2 * v + 1].mi + T[2*v + 1].g) > d) {
v = v * 2 + 1;
l = mid + 1;
} else {
mx = max(mx, T[2 * v + 1].mx + T[2*v + 1].g);
mi = min(mi, T[2 * v + 1].mi + T[2*v + 1].g);
v = v * 2;
r = mid;
}
}
mi = min(mi, T[v].g + T[v].mi);
mx = max(mx, T[v].g + T[v].mx);
return {l, mi, mx};
}
pair<ll,ll>qr(int a, int b, int l, int r, int v) {
if(a <= l && r <= b) {
return {T[v].mi + T[v].g, T[v].mx + T[v].g};
}
int mid = (l + r) / 2;
prop(v);
pair<ll,ll>w = {INF, -INF};
if(a <= mid) {
auto y = qr(a, b, l, mid, v * 2);
w = {min(w.ST, y.ST), max(w.ND, y.ND)};
}
if(mid < b) {
auto y = qr(a, b, mid + 1, r, v * 2 + 1);
w = {min(w.ST, y.ST), max(w.ND, y.ND)};
}
T[v].mi = min(T[2*v].mi + T[2*v].g, T[2*v+1].mi + T[2*v+1].g);
T[v].mx = max(T[2*v].mx + T[2*v].g, T[2*v+1].mx + T[2*v+1].g);
return w;
}
vi distribute_candies(vi c, vi la, vi ra, vi v) {
n = (int)c.size();
q = (int)la.size();
for(int i = 0; i < q; ++i) {
events[la[i]].PB(i + 1);
events[ra[i] + 1].PB(-i - 1);
}
q++;
vi ans(n);
for(int i = 0; i < n; ++i) {
for(int x : events[i]) {
if(x > 0) {
add(x, q - 1, 0, q - 1, v[x - 1], 1);
} else {
x = -x;
add(x, q - 1, 0, q - 1, -v[x - 1], 1);
}
}
auto [pos, mi, mx] = ask(c[i]);
//cout << pos << " " << mi << " " << mx << "\n";
auto zz = qr(q - 1, q - 1, 0, q - 1, 1);
if(mx - mi <= c[i]) {
auto z2 = qr(0, q - 1, 0, q - 1, 1);
ans[i] = zz.ST - z2.ST;
} else {
auto z = qr(pos + 1, q - 1, 0, q - 1, 1);
if(mi < z.ST) {
ans[i] = c[i] - (z.ND - zz.ST);
} else {
ans[i] = zz.ST - z.ST;
}
}
}
return ans;
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int N, Q;
//cin >> N >> Q;
//vi c(N), l(Q), r(Q), v(Q);
//for(int i = 0; i < N; ++i) {
//cin >> c[i];
//}
//for(int i = 0; i < Q; ++i) {
//cin >> l[i] >> r[i] >> v[i];
//}
//auto ans = distribute_candies(c,l,r,v);
//for(int x : ans) cout << x << " ";
//}
