#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_4 = 1;
REP(i,q) if (l[i] != 0 || r[i] != n-1) sub_4 = 0;
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_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;
}
