#include <bits/stdc++.h>
#define F first
#define S second
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define bck(i, a, b) if ((i) >= (a) && (i) < (b))
#define trav(x, a) for (auto &x : (a))
#define sz(a) (int)(a).size()
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define dbg(X) std::cerr << "[DBG]("<<__FUNCTION__<<":"<<__LINE__<<") " << #X << ": " << X << std::endl;
using namespace std;
typedef long long ll;
typedef string str;
template<typename T> using vec = vector<T>;
template<typename T> using pq = priority_queue<T, vector<T>, std::greater<T>>;
template<typename T> using mxpq = priority_queue<T>;
typedef pair<int,int> pii;
typedef vec<int> vi;
typedef vec<pii> vii;
typedef vec<vi> vvi;
typedef pair<ll,ll> pll;
typedef vec<ll> vl;
typedef vec<pll> vll;
typedef vec<vl> vvl;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename A, typename B>
istream& operator>>(istream& s, pair<A,B>& p) { return s>>p.first>>p.second; }
template<typename A, typename B>
ostream& operator<<(ostream& s, const pair<A,B>& p) { s << "(" << p.F << ", " << p.S << ")"; return s; }
template<typename T>
istream& operator>>(istream& s, vec<T>& p) { for (T& t : p) s >> t; return s; }
template<typename T>
ostream& operator<<(ostream& s, const vec<T>& p) { for (const T& t : p) s << t << " "; return s; }
// monoid
struct S {
// id
ll mn = LLONG_MAX, mx = LLONG_MIN;
int mni, mxi;
int i = INT_MAX;
int len = 0;
S() {}
S(ll v, int j) : mn(v), mx(v), mni(j), mxi(j), i(j), len(1) {}
S(ll mn, ll mx, int mni, int mxi, int j, int len) : mn(mn), mx(mx), mni(mni), mxi(mxi), i(j), len(len) {}
S operator+(S o) {
if (mn < o.mn) o.mn = mn, o.mni = mni;
else if (mn == o.mn) ckmin(o.mni, mni);
if (mx > o.mx) o.mx = mx, o.mxi = mxi;
else if (mx == o.mx) ckmin(o.mxi, mxi);
ckmin(o.i, i);
o.len += len;
return o;
}
};
// update
struct U {
ll v = 0;
static U add(ll x) { return {x}; }
// apply
S operator()(S a) {
a.mn += v;
a.mx += v;
return a;
}
// compose
U operator()(U o) {
return o.v += v, o;
}
};
struct seg {
int l, r;
S v; U u;
seg *lt=0, *rt=0;
seg(const vl& a) : seg(a, 0, sz(a)) {}
seg(const vl& a, int l, int r) : l(l), r(r) {
if (l+1 == r) v = S(a[l], l);
else {
int m = (l+r)/2;
lt = new seg(a, l, m);
rt = new seg(a, m, r);
v = lt->v + rt->v;
}
}
void update(int s, int e, U upd) {
if (l >= e || r <= s) return;
if (l >= s && r <= e) u = upd(u);
else {
push();
lt->update(s, e, upd);
rt->update(s, e, upd);
pull();
}
}
S query(int s, int e) {
if (e <= l || s >= r) return S();
if (l >= s && r <= e) return u(v);
else return u(lt->query(s,e) + rt->query(s,e));
}
S bs(int cap, S s=S()) {
auto e = u(v) + s;
if (e.mx - e.mn <= cap) return e;
else if (l+1 == r) return s;
else {
push();
pull();
e = rt->u(rt->v) + s;
if (e.mx - e.mn <= cap) return lt->bs(cap, e);
else return rt->bs(cap, s);
}
}
void pull() { v = lt->u(lt->v) + rt->u(rt->v); }
void push() {
lt->u = u(lt->u);
rt->u = u(rt->u);
u = U();
}
};
vi distribute_candies(vi i1, vi i2, vi i3, vi i4) {
int n = sz(i1);
int q = sz(i2);
vl c(all(i1));
vec<pair<pii, ll>> u(sz(i2));
rep(i, 0, sz(i2)) u[i] = {{i2[i], i3[i]}, i4[i]};
trav(v, u) v.F.S++;
vii ev;
rep(i,0,n) ev.pb({i, INT_MAX});
rep(i,0,q) ev.pb({u[i].F.F, i}), ev.pb({u[i].F.S, -i-1});
sort(all(ev));
seg s((vl(q+1)));
vi ans(n);
trav(e, ev) {
auto [ai, qi] = e;
if (qi == INT_MAX) {
S rr = s.bs(c[ai]);
int r = rr.i;
S w = s.query(r, q+1);
ll x = s.query(q, q+1).mn;
ans[ai] = x - w.mn;
if (r) {
ll g = s.query(r-1, r).mn;
if (g < w.mn) {
ans[ai] = x - w.mx + c[ai];
}
}
} else if (qi >= 0) {
s.update(qi+1, q+1, U::add(u[qi].S));
} else {
qi = -qi-1;
s.update(qi+1, q+1, U::add(-u[qi].S));
}
}
return ans;
}
