#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
typedef long long ll;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), q = v.size();
vector<int> a(n);
int sub_1 = n <= 2000 && q <= 2000;
int sub_2 = 1;
REP(i,q) if (v[i] < 0) sub_2 = 0;
int sub_3 = *min_element(c.begin(),c.end()) == *max_element(c.begin(),c.end());
int sub_4 = 1;
REP(i,q) if (l[i] != 0 || r[i] != n-1) sub_4 = 0;
int sub_5 = ! (sub_1+sub_2+sub_3+sub_4);
if (sub_1) {
REP(i,q) {
for (int j = l[i]; j <= r[i]; ++j) {
a[j] += v[i];
a[j] = max(0, min(c[j], a[j]));
}
}
} else if (sub_2) {
int base = 1;
while (base < n) base *= 2;
vector<ll> tree(2*base);
auto add = [&](int xl, int xr, int v) {
xl += base;
xr += base;
tree[xl] += v;
if (xl == xr) return;
tree[xr] += v;
while (xl/2 != xr/2) {
if (~xl&1) tree[xl+1] += v;
if (xr&1) tree[xr-1] += v;
xl /= 2;
xr /= 2;
}
};
REP(i,q) {
add(l[i], r[i], v[i]);
}
REP(i,base) {
tree[2*i] += tree[i];
tree[2*i+1] += tree[i];
}
REP(i,n) {
a[i] = min(tree[base+i], ll(c[i]));
}
} else if (sub_3 || sub_5) {
const int max_C = 1000000000;
const int C = sub_5 ? max_C : c[0];
int base = 1;
while (base < n) base *= 2;
struct info {
int x1, y1, y2;
int last;
info(int x1, int y1, int y2, int last) : x1(x1), y1(y1), y2(y2), last(last) { }
int get_y(int x) const {
int x2 = x1 + y2 - y1;
if (x <= x1) return y1;
if (x >= x2) return y2;
return x - x1 + y1;
}
};
auto merge = [&](const info& G, const info& F) {
// G( F(x) )
int y1 = G.get_y(F.y1), y2 = G.get_y(F.y2);
int x1 = y1 == y2 ? 0 : F.x1 + max(0, G.x1 - F.y1);
int sgn = G.last ?: F.last;
return info{ x1, y1, y2, sgn };
};
auto single = [&](int val) {
int v = min(abs(val), C);
if (val >= 0) return info{ 0, v, C, 1 };
else return info{ v, 0, C-v, -1 };
};
vector<info> tree(2*base, info{ 0, 0, C, 0 });
auto push = [&](int no) {
tree[2*no] = merge(tree[no], tree[2*no]);
tree[2*no+1] = merge(tree[no], tree[2*no+1]);
tree[no] = info{ 0, 0, C, 0 };
};
function<void(int,int,int,int,int,const info&)>
add = [&](int no, int tl, int tr, int xl, int xr, const info& in) {
if (xr < tl || tr < xl) {
} else if (xl <= tl && tr <= xr) {
tree[no] = merge(in, tree[no]);
} else {
push(no);
int ts = (tl+tr)/2;
add(2*no, tl, ts, xl, xr, in);
add(2*no+1, ts+1, tr, xl, xr, in);
}
};
REP(i,q) {
add(1, 0, base-1, l[i], r[i], single(v[i]));
}
REP(i,base) {
push(i);
}
REP(i,n) {
info& in = tree[base+i];
if (sub_3) {
a[i] = in.y1;
} else {
if (in.y1 + max_C - in.y2 >= c[i]) {
a[i] = in.y1;
} else if (in.last > 0) {
a[i] = min(in.y1, c[i]);
} else {
a[i] = max(c[i] - (max_C - in.y2), 0);
}
}
}
} else if (sub_4) {
vector<int> idx(n);
REP(i,n) idx[i] = i;
sort(idx.begin(), idx.end(), [&](int i, int j) { return c[i] < c[j]; });
int ptr = 0;
struct info {
int a,b,c;
info() : a(0), b(0), c(0) { }
} in;
REP(_i,q) {
int i = q-1-_i;
in.a -= v[i];
while (ptr < n) {
int j = idx[ptr];
if (in.a >= c[j]) {
a[j] = in.b;
} else if (in.a <= in.c - c[j]) {
a[j] = c[j] - (in.c - in.b);
} else {
break;
}
++ptr;
}
if (in.a < 0) {
in.c -= in.a;
in.b -= in.a;
in.a = 0;
} else {
in.c = max(in.c, in.a);
}
}
while (ptr < n) {
int j = idx[ptr];
a[j] = in.b;
++ptr;
}
}
return a;
}
