#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#define ll long long
#define all(x) (x).begin(), (x).end()
const int mxn = 1e5 + 100;
struct S {
ll W, A, B;
};
bool operator < (S a, S b) {
if (a.W != b.W) return a.W < b.W;
if (a.A != b.A) return a.A < b.A;
return a.B < b.B;
}
struct O {
ll diff, indI, indJ;
};
bool operator < (O a, O b) {
if (a.diff != b.diff) return a.diff < b.diff;
if (a.indI != b.indI) return a.indI < b.indI;
return a.indJ < b.indJ;
}
ll res = 0;
ll ldr[mxn], rnk[mxn], ans[mxn], L[mxn], R[mxn], sumA[mxn], sumB[mxn], mnOddS[mxn], mnEvenS[mxn], mnOddJ[mxn], mnEvenJ[mxn];
void umin(ll &x, ll y) {
x = min(x, y);
}
void umax(ll &x, ll y) {
x = max(x, y);
}
int Find(int x) {
if (ldr[x] == x) return x;
return ldr[x] = Find(ldr[x]);
}
bool Same(int x, int y) {
return Find(x) == Find(y);
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) return;
if (rnk[y] > rnk[x]) swap(x, y);
ldr[y] = x;
rnk[x] += rnk[y];
sumA[x] += sumA[y];
sumB[x] += sumB[y];
umin(L[x], L[y]);
umax(R[x], R[y]);
umin(mnOddS[x], mnOddS[y]);
umin(mnEvenS[x], mnEvenS[y]);
umin(mnOddJ[x], mnOddJ[y]);
umin(mnEvenJ[x], mnEvenJ[y]);
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = W.size(), Q = (int) E.size();
vector<ll> Res(Q, 0);
vector<pair<ll, ll>> Qr;
for (int i = 0; i < Q; i++) Qr.push_back({E[i], i});
sort(all(Qr));
vector<S> V;
for (int i = 0; i < N; i++) V.push_back({W[i], A[i], B[i]}), res += A[i];
sort(all(V));
for (int i = 0; i < N; i++) {
ldr[i] = i, L[i] = i, R[i] = i;
ans[i] = V[i].A;
rnk[i] = 1, sumA[i] = V[i].A, sumB[i] = V[i].B;
mnOddS[i] = mnEvenS[i] = mnOddJ[i] = mnEvenJ[i] = 1e15;
}
vector<O> Ord;
for (int i = 0; i < N; i++) {
if (i + 1 < N) Ord.push_back({V[i + 1].W - V[i].W, i, i + 1});
if (i + 2 < N) Ord.push_back({V[i + 2].W - V[i].W, i, i + 2});
}
sort(all(Ord));
int last = 0;
for (auto x : Qr) {
while (last < Ord.size() && Ord[last].diff <= x.first) {
int indI = Ord[last].indI, indJ = Ord[last].indJ;
// cout << indI << " " << indJ << " : " << Ord[last].diff << endl;
if (!Same(indI, indJ)) {
res -= ans[Find(indI)];
res -= ans[Find(indJ)];
Union(indI, indJ);
}
else res -= ans[Find(indI)];
int X = Find(indI), posL = L[X], posR = R[X];
// cout << X << " - " << L[X] << " " << R[X] << endl;
if (indI + 1 == indJ) {
bool even = (indI % 2 == 0);
if (even) umin(mnEvenS[X], V[indI].A - V[indI].B);
else umin(mnOddS[X], V[indI].A - V[indI].B);
even = (indJ % 2 == 0);
// if (indJ == 4) {
// cout << "SURPRISE MOTHERFUCKER : " << even << " " << V[indJ].A - V[indJ].B << endl;
// }
if (even) umin(mnEvenS[X], V[indJ].A - V[indJ].B);
else umin(mnOddS[X], V[indJ].A - V[indJ].B);
}
else {
int ind = indI + 1;
bool even = (ind % 2 == 0);
if (even) umin(mnEvenJ[X], V[ind].A - V[ind].B);
else umin(mnOddJ[X], V[ind].A - V[ind].B);
}
if (rnk[X] % 2 == 0) ans[X] = sumB[X];
else {
ll least = 1e15;
if (posL % 2 == 0) umin(least, mnEvenS[X]), umin(least, mnOddJ[X]);
else umin(least, mnOddS[X]), umin(least, mnEvenJ[X]);
// cout << "! " << sumB[X] << " " << least << endl;
ans[X] = sumB[X] + least;
}
res += ans[X];
// cout << res << endl;
last++;
}
// cout << endl;
Res[x.second] = res;
}
return Res;
}
