#include <bits/stdc++.h>
using namespace std;
vector<int> ww;
set<pair<int, int>> st;
vector<bool> odd, sub;
long long ss;
struct DSU {
vector<int> f, mn, mx, ev, od;
long long s;
DSU(int n) {
f.resize(n, -1);
ev.resize(n, -1e9);
od.resize(n, -1e9);
mn.resize(n);
mx.resize(n);
iota(mn.begin(), mn.end(), 0);
iota(mx.begin(), mx.end(), 0);
s = 0;
}
void set(int i, int x) {
if (i & 1) {
od[i] = x;
} else {
ev[i] = x;
}
}
int find(int u) {
return f[u] < 0 ? u : f[u] = find(f[u]);
}
void unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (f[u] > f[v]) swap(u, v);
if (f[u] != -1 && (f[u] & 1)) {
if (sub[u]) {
ss -= ((mn[u] & 1) ? od[u] : ev[u]) - max(od[u], ev[u]);
sub[u] = 0;
}
s -= ((mn[u] & 1) ? od[u] : ev[u]);
if (odd[u]) {
st.erase({ww[mx[u]] - ww[mn[u]], u});
odd[u] = 0;
}
}
if (f[v] != -1 && (f[v] & 1)) {
if (sub[v]) {
ss -= ((mn[v] & 1) ? od[v] : ev[v]) - max(od[v], ev[v]);
sub[v] = 0;
}
s -= ((mn[v] & 1) ? od[v] : ev[v]);
if (odd[v]) {
st.erase({ww[mx[v]] - ww[mn[v]], v});
odd[v] = 0;
}
}
f[u] += f[v];
f[v] = u;
mn[u] = min(mn[u], mn[v]);
mx[u] = max(mx[u], mx[v]);
od[u] = max(od[u], od[v]);
ev[u] = max(ev[u], ev[v]);
if (f[u] & 1) {
s += ((mn[u] & 1) ? od[u] : ev[u]);
st.insert({ww[mx[u]] - ww[mn[u]], u});
odd[u] = 1;
}
}
};
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int n = w.size();
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](const int &i, const int &j) {
return w[i] < w[j];
});
auto tw = w, ta = a, tb = b;
for (int i = 0; i < n; i++) {
w[i] = tw[id[i]];
a[i] = ta[id[i]];
b[i] = tb[id[i]];
}
ww = w;
odd = vector<bool> (n), sub = vector<bool> (n);
vector<pair<int, int>> q, q2;
for (int i = 0; i + 1 < n; i++) {
q.push_back({w[i + 1] - w[i], i});
}
for (int i = 0; i + 2 < n; i++) {
q2.push_back({w[i + 2] - w[i], i});
}
sort(q.begin(), q.end());
sort(q2.begin(), q2.end());
DSU ds(n);
ss = 0;
for (int i = 0; i < n; i++) {
ss += a[i];
ds.set(i, b[i] - a[i]);
}
int m = e.size();
vector<pair<int, int>> ne(m);
for (int i = 0; i < m; i++) {
ne[i] = {e[i], i};
}
sort(ne.begin(), ne.end());
vector<long long> ans(m);
vector<bool> vis(n);
for (int i = 0, j = 0, k = 0; i < m; i++) {
while (j + 1 < n && q[j].first <= ne[i].first) {
ds.unite(q[j].second, q[j].second + 1);
if (!vis[q[j].second]) {
vis[q[j].second] = 1;
ss += b[q[j].second] - a[q[j].second];
}
if (!vis[q[j].second + 1]) {
vis[q[j].second + 1] = 1;
ss += b[q[j].second + 1] - a[q[j].second + 1];
}
j++;
}
while (st.size()) {
auto [x, u] = *st.begin();
if (x > ne[i].first) break;
st.erase(st.begin());
ss += ((ds.mn[u] & 1) ? ds.od[u] : ds.ev[u]) - max(ds.od[u], ds.ev[u]);
odd[u] = 0;
sub[u] = 1;
}
ans[ne[i].second] = ss - ds.s;
}
return ans;
}
