// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,sse2,sse3,ssse3,sse4,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "candies.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define point pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define show(x) cerr << (#x) << " = " << x << '\n'
#define print(x) if (1) {cerr << (#x) << " = "; for (auto it : x) \
cerr << it << ' '; cerr << '\n';}
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0)
const int N = 1 << 19;
const int S = 5e6 + 64;
const int INF = 2e9 + 64;
const ll MAX = 2e18 + 64;
const int LOG = 25;
const int MOD = 1e9 + 7; //998244353;
const int P = 79;
const int B = 800;
using namespace std;
using namespace __gnu_pbds;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
int q = v.size();
vector<point> a(n);
for (int i = 0; i < n; ++i)
a[i] = {c[i], i};
sort(all(a));
vector<ll> pref(q), suf(q);
pref.front() = v.front(), suf.back() = v.back();
for (int i = 1; i < q; ++i)
pref[i] = pref[i - 1] + v[i];
for (int i = q - 2; i >= 0; --i)
suf[i] = suf[i + 1] + v[i];
suf.pb(0);
vector<ll> mn(q), mx(q);
mn[q - 1] = mx[q - 1] = pref[q - 1];
for (int i = q - 2; i >= 0; --i)
mn[i] = min(mn[i + 1], pref[i]), mx[i] = max(mx[i + 1], pref[i]);
vector<int> w(n), ans(n);
int j = -1;
for (int i = n - 1; i >= 0; --i) {
if (i + 1 < n)
w[i] = min(a[i].X, w[i + 1]);
assert(w[i] >= 0 && w[i] <= a[i].X);
//show(j);
while ((j + 1 < q) && ((mx[j + 1] - (j >= 0 ? pref[j] : 0) + w[i] >= a[i].X)
|| (mn[j + 1] - (j >= 0 ? pref[j] : 0) + w[i] <= 0))) {
++j;
w[i] += v[j];
w[i] = max(0, min(a[i].X, w[i]));
}
//show(i), show(j), show(w[i]);
ans[a[i].Y] = w[i] + suf[j + 1];
}
return ans;
}
