#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];
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) {
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;
int cnt = 0;
cont.push_back({});
while (1) {
if (it->first == 1e10) break;
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 (!cnt) cont.back().push_back(*it), toDelete.push_back(*it);
toDelete.push_back(*nxt);
cont.back().push_back(*nxt);
cnt++;
}
else {
cnt = 0;
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;
if (i) sum += get(l, v[i].first - 1);
if (i < v.size() - 1) sum += get(v[i].second.first + 1, r);
newAns = min(newAns, sum);
}
for (int i = 0; i < v.size() - 1; i++) {
int pos = v[i].second.first;
if (pos == l) continue;
if (V[pos + 1].w - V[pos - 1].w <= x.first) newAns = min(newAns, get(l, pos - 1) + get(pos + 1, r) + V[pos].a);
}
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;
}
