#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) (x).begin(), (x).end()
struct S {
ll w, a, b;
};
bool csort(S a, S b) {
if (a.w != b.w) return a.w < b.w;
return a.a < b.a;
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = A.size(), Q = (int) E.size();
vector<pair<ll, ll>> ord;
for (int i = 0; i < Q; i++) ord.push_back({E[i], i});
sort(all(ord));
vector<S> V;
for (int i = 0; i < N; i++) V.push_back({W[i], A[i], B[i]});
sort(all(V), csort);
vector<ll> res(Q, 0);
ll ans = 0;
set<pair<ll, pair<ll, ll>>> s;
s.insert({-1e10, {-1e10, 0}});
s.insert({1e10, {1e10, 0}});
for (int i = 0; i < N; i++) {
s.insert({i, {i, V[i].a}});
ans += V[i].a;
}
ll prf[N + 2];
memset(prf, 0, sizeof(prf));
prf[0] = V[0].b;
for (int i = 1; i < N; i++) prf[i] = prf[i - 1] + V[i].b;
auto get = [&] (int l, int r) {
if (l < 0 || r >= N || l > r) return 0LL;
return prf[r] - (l == 0 ? 0 : prf[l - 1]);
};
for (auto x : ord) {
vector<pair<ll, pair<ll, ll>>> toDelete, toAdd;
auto it = s.begin();
it++;
vector<vector<pair<ll, pair<ll, ll>>>> cont;
cont.push_back({});
while (1) {
auto nxt = it;
nxt++;
ll first = it->second.first, last = nxt->first;
if (last == 1e10) break;
if (V[last].w - V[first].w <= x.first) {
if (!cont.back().size()) cont.back().push_back(*it), toDelete.push_back(*it);
toDelete.push_back(*nxt);
cont.back().push_back(*nxt);
}
else if (cont.back().size()) cont.push_back({});
it++;
}
for (auto v : cont) {
if (!v.size()) continue;
ll l = v[0].first, r = v.back().second.first;
ll len = r - l + 1;
if (len % 2 == 0) {
toAdd.push_back({l, {r, get(l, r)}});
continue;
}
ll newAns = 1e15;
for (int i = 0; i < v.size(); i++) {
ll sum = v[i].second.second;
sum += get(l, v[i].first - 1);
sum += get(v[i].second.first + 1, r);
newAns = min(newAns, sum);
}
for (int i = 0; i < v.size(); i++) {
int posL = v[i].first, posR = v[i].second.first;
if (posR - posL + 1 <= 1) continue;
if (i) {
if ((posL - l) % 2 == 0) newAns = min(newAns, get(l, posL - 1) + A[posL] + get(posL + 1, r));
else if (V[posL + 1].w - V[posL - 1].w <= x.first) newAns = min(newAns, get(l, posL - 1) + A[posL] + get(posL + 1, r));
}
if (i + 1 < v.size()) {
if ((r - posR) % 2 == 0) newAns = min(newAns, get(l, posR - 1) + A[posR] + get(posR + 1, r));
else if (V[posR + 1].w - V[posR - 1].w <= x.first) newAns = min(newAns, get(l, posR - 1) + A[posR] + get(posR + 1, r));
}
}
toAdd.push_back({l, {r, newAns}});
}
for (auto el : toDelete) {
s.erase(s.find(el));
ans -= el.second.second;
}
for (auto el : toAdd) {
s.insert(el);
ans += el.second.second;
}
res[x.second] = ans;
}
return res;
}
