/**
* 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;
vector<ll> p(N+1);
struct node {
ll set, sum, lz;
node() {
set = -1, sum = 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].sum = tree[x].set = v;
tree[x].lz = 0;
}
void add(int x, int v) {
tree[x].sum += v, tree[x].lz += v;
}
void push(int x, int y, int lx, int rx, int lef) {
if (tree[x].set != -1) {
if (tree[x].set == 0)apply(y, tree[x].set);
else {
int mid = lx+rx>>1;
apply(y, (!lef?p[mid]-p[lx]:p[rx-mid]));
}
tree[x].set = -1;
}
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);
return;
}
node a = tree[x];
push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1);
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].sum = tree[2*x+1].sum+tree[2*x+2].sum;
}
void radd(int l, int r, int v) {
radd(l, r, v, 0, 0, size);
}
void set0(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx)return;
if (lx >= l && rx <= r) {
apply(x, 0);
return;
}
node a = tree[x];
push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1);
int mid = lx+rx>>1;
set0(l, r, 2*x+1, lx, mid);
set0(l, r, 2*x+2, mid, rx);
tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum;
}
void set0(int l, int r) {
set0(l, r, 0, 0, size);
}
void setmx(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx)return;
if (lx >= l && rx <= r) {
tree[x].sum = tree[x].set = p[rx]-p[lx];
tree[x].lz = 0;
return;
}
node a = tree[x];
push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1);
int mid = lx+rx>>1;
setmx(l, r, 2*x+1, lx, mid);
setmx(l, r, 2*x+2, mid, rx);
tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum;
}
void setmx(int l, int r) {
setmx(l, r, 0, 0, size);
}
int get(int i, int x, int lx, int rx) {
if (rx-lx==1)return tree[x].sum;
int mid = lx+rx>>1;
node a = tree[x];
push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1);
if (i < mid)return get(i, 2*x+1, lx, mid);
else return get(i, 2*x+2, mid, rx);
tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum;
}
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);
for (int i = 1; i <= n; ++i)p[i] = c[i-1]+p[i-1];
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) {
int a = st.get(i);
if (a <= c[0])continue;
int lx = 0, rx = n;
while (rx-lx>1) {
int mid = lx+rx>>1;
if (st.get(mid) <= c[mid])rx = mid;
else lx = mid;
}
st.setmx(0, lx+1);
}
if (v[i] < 0){
int a = st.get(i);
if (a >= 0)continue;
int lx = 0, rx = n;
while (rx-lx>1) {
int mid = lx+rx>>1;
if (st.get(mid) >= 0)rx = mid;
else lx = mid;
}
st.set0(0, lx+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}, {2, 2}, {20, -100});
// for (auto &i: ans)cout << i << " ";
// return 0;
// }
