#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<ii,int>
#define pb push_back
const int MAX = (int) 2e5;
int n;
int a[MAX + 5];
int q;
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];
vector<int> ans;
namespace sub4 {
ll s[MAX + 5];
ll smax[MAX + 5], smin[MAX + 5];
ll dis[MAX + 5];
bool check() {
for(int i = 1; i <= q; ++i) if(query[i].l != 1 || query[i].r != n) return 0;
return 1;
}
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]);
for(int i = q - 1; i >= 1; --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 = n + 1;
while(hi - lo > 1) {
int mid = lo + hi >> 1;
if(dis[mid] <= a[i]) hi = mid;
else lo = mid;
}
// cout << hi << " ";
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 = 0; i < q; ++i) query[i + 1] = queries(l[i] + 1, r[i] + 1, v[i]);
if(sub4::check()) sub4::solve();
return ans;
}
