#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX = (int) 1e5;
int n, q;
int a[MAX + 5];
vector<int> ans;
struct queries {
int l, r, v;
queries(int _l = 0, int _r = 0, int _v = 0) : l(_l), r(_r), v(_v) {}
} query[MAX + 5];
namespace sub4 {
bool check() {
for(int i = 1; i <= q; ++i) if(query[i].l != 1 || query[i].r != n) return 0;
return 1;
}
ll s[MAX + 5], smax[MAX + 5], smin[MAX + 5], dis[MAX + 5];
void solve() {
for(int i = 1; i <= q; ++i) s[i] = s[i - 1] + query[i].v;
smax[q] = smin[q] = s[q];
for(int i = q - 1; i >= 1; --i) {
smax[i] = max(smax[i + 1], s[i]);
smin[i] = min(smin[i + 1], s[i]);
}
for(int i = 1; i <= q; ++i) dis[i] = max(smax[i] - s[i - 1], 0LL) - min(smin[i] - s[i - 1], 0LL);\
for(int i = 1; i <= n; ++i) {
int lo = 0, hi = q + 1;
while(hi - lo > 1) {
int mid = lo + hi >> 1;
if(dis[mid] <= a[i]) hi = mid;
else lo = mid;
}
int c;
if(hi == 1) c = -1;
else c = (query[hi - 1].v < 0) ? -1 : 1;
if(c == -1) ans.pb(s[q] - s[hi - 1]);
else ans.pb(a[i] + s[q] - s[hi - 1]);
}
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size();
for(int i = 0; i < n; ++i) a[i + 1] = c[i];
q = l.size();
for(int i = 1; i <= q; ++i) query[i] = queries(l[i - 1] + 1, r[i - 1] + 1, v[i - 1]);
if(sub4::check()) sub4::solve(), 0;
return ans;
}
