/**
* 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 = uint64_t;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long
const char nl = '\n';
const int N = 2e5+1;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int mod = 1e9+7;
int C;
struct node {
int set, mn, mx, lz;
node() {
set = -1, mn = 0, mx = 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 apply(int x, int v) {
tree[x].mn = tree[x].mx = tree[x].set = v;
tree[x].lz = 0;
}
void add(int x, int v) {
tree[x].mn += v;
tree[x].mx += v;
tree[x].lz += v;
}
void push(int x, int y) {
if (tree[x].set != -1) {
apply(y, tree[x].set);
tree[x].set = -1, tree[y].lz = 0;
}
if (tree[x].lz != 0) {
add(y, tree[x].lz);
tree[x].lz = 0;
}
}
void radd(int l, int r, int v, int x, int lx, int rx) {
if (rx <= l || r <= lx)return;
if (lx >= l && rx <= r) {
add(x, v);
//cout << tree[x].mn << " " << tree[x].mx << " " << tree[x].set << " " << tree[x].lz << nl;
return;
}
node a = tree[x];
push(x, 2*x+1); tree[x] = a; push(x, 2*x+2);
int mid = lx+rx>>1;
radd(l, r, v, 2*x+1, lx, mid);
radd(l, r, v, 2*x+2, mid, rx);
tree[x].mn = min(tree[2*x+1].mn, tree[2*x+2].mn);
tree[x].mx = max(tree[2*x+1].mx, tree[2*x+2].mx);
}
void radd(int l, int r, int v) {
radd(l, r, v, 0, 0, size);
}
void minimize(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx || tree[x].mx <= C)return;
if (lx >= l && rx <= r)
if (tree[x].mn > C) {
apply(x, C);
return;
}
node a = tree[x];
push(x, 2*x+1); tree[x] = a; push(x, 2*x+2);
int mid = lx+rx>>1;
minimize(l, r, 2*x+1, lx, mid);
minimize(l, r, 2*x+2, mid, rx);
tree[x].mn = min(tree[2*x+1].mn, tree[2*x+2].mn);
tree[x].mx = max(tree[2*x+1].mx, tree[2*x+2].mx);
}
void minimize(int l, int r) {
minimize(l, r, 0, 0, size);
}
void maximize(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx || tree[x].mn >= 0)return;
if (lx >= l && rx <= r)
if (tree[x].mx < 0) {
apply(x, 0);
return;
}
node a = tree[x];
push(x, 2*x+1); tree[x] = a; push(x, 2*x+2);
int mid = lx+rx>>1;
maximize(l, r, 2*x+1, lx, mid);
maximize(l, r, 2*x+2, mid, rx);
tree[x].mn = min(tree[2*x+1].mn, tree[2*x+2].mn);
tree[x].mx = max(tree[2*x+1].mx, tree[2*x+2].mx);
}
void maximize(int l, int r) {
maximize(l, r, 0, 0, size);
}
int get(int i, int x, int lx, int rx) {
if (rx-lx==1) {
//cout << tree[x].mn << nl;
assert(tree[x].mn == tree[x].mx);
return tree[x].mn;
}
int mid = lx+rx>>1;
node a = tree[x];
push(x, 2*x+1); tree[x] = a; push(x, 2*x+2);
if (i < mid)return get(i, 2*x+1, lx, mid);
else return get(i, 2*x+2, mid, rx);
tree[x].mn = min(tree[2*x+1].mn, tree[2*x+2].mn);
tree[x].mx = max(tree[2*x+1].mx, tree[2*x+2].mx);
}
int get(int i) {
return get(i, 0, 0, size);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int n = sz(c), q = sz(l);
C = c[0];
segtree st; st.init(n+1);
for (int i = 0; i < q; ++i) {
st.radd(l[i], r[i]+1, v[i]);
if (v[i] > 0)st.minimize(l[i], r[i]+1);
if (v[i] < 0)st.maximize(l[i], r[i]+1);
}
vector<int> res(n);
for (int i = 0; i < n; ++i)res[i] = st.get(i);
return res;
}
//int main() {
//vector<int> ans = distribute_candies({15, 15, 15}, {0, 0}, {1, 2}, {10, 100});
//for (auto &i: ans)cout << i << " ";
//return 0;
//}
