#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#define fileio() freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define cmprs(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)(a.size())
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int dx[] = {1,-1,0,0,1,1,-1,-1};
const int dy[] = {0,0,1,-1,1,-1,1,-1};
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 101010;
ll bsum[MAX];
ll ans=0;
struct segtr{
//0-indexed!
vector<ll> tr;
int n;
void rst(int sz) {
n=sz;
tr.resize((n+1)<<1,LINF);
}
void upd(int i, ll v) {
tr[i+n] = min(tr[i+n], v); i+=n; //AWARE OF UPD POLICY!!
for (i>>=1; i; i>>=1) tr[i] = min(tr[i<<1], tr[i<<1|1]);
}
ll qry(int l, int r) {
ll ret = LINF;
for (l+=n, r+=n; l<=r; l>>=1, r>>=1) {
if (l&1) ret = min(ret, tr[l++]);
if (~r&1) ret = min(ret, tr[r--]);
}
return ret;
}
} seg1[2],seg2[2];
struct dsu {
int n;
vector<int> p,s;
vector<pii> rng;
vector<ll> v;
void rst(int _n) {
n=_n+10;
p.resize(n);
v.resize(n);
s.resize(n,1);
rng.resize(n);
iota(all(p),0);
for (int i=0; i<n; i++) rng[i]={i,i};
}
int fd(int a) {
if (a==p[a]) return a;
return p[a]=fd(p[a]);
}
int mg(int a, int b) {
a=fd(a), b=fd(b);
if (a==b) return 0;
auto [l1,r1]=rng[a]; auto [l2,r2]=rng[b];
int l3=min(l1,l2),r3=max(r1,r2);
ll val=0;
if ((s[a]+s[b])%2==0) {
ans-=(v[a]+v[b]);
ans+=bsum[r3]-bsum[l3-1];
val=bsum[r3]-bsum[l3-1];
}
else {
val=v[a]+v[b];
ans-=(v[a]+v[b]);
val=min(val,seg1[l3%2].qry(l3,r3)+bsum[r3]-bsum[l3-1]);
val=min(val,seg2[l3%2].qry(l3,r3)+bsum[r3]-bsum[l3-1]);
ans+=val;
}
p[b]=a;
s[a]+=s[b], s[b]=0;
rng[a]={l3,r3}, rng[b]={-1,0};
v[a]=val;
return 1;
}
} uf;
typedef array<ll,3> arr;
int n,q;
arr a[MAX];
pll qry[MAX];
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
n=sz(W),q=sz(E);
for (int i=1; i<=n; i++) a[i][0]=W[i-1];
for (int i=1; i<=n; i++) a[i][1]=A[i-1];
for (int i=1; i<=n; i++) a[i][2]=B[i-1];
vector<ll> ret(q);
sort(a+1,a+n+1);
for (int i=0; i<q; i++) qry[i]={E[i],i};
sort(qry,qry+q);
priority_queue<pll,vector<pll>,greater<pll>> pq1,pq2;
for (int i=1; i+1<=n; i++) pq1.push({a[i+1][0]-a[i][0],i});
for (int i=1; i+2<=n; i++) pq2.push({a[i+2][0]-a[i][0],i});
seg1[0].rst(MAX),seg1[1].rst(MAX);
seg2[0].rst(MAX),seg2[1].rst(MAX);
uf.rst(MAX);
for (int i=1; i<=n; i++) {
uf.v[i]=a[i][1];
ans+=a[i][1];
bsum[i]=bsum[i-1]+a[i][2];
}
for (int i=0; i<q; i++) {
auto [d,qi]=qry[i];
vector<pii> idx;
while (!pq1.empty() && pq1.top().first<=d) {
auto [dif,i1]=pq1.top(); pq1.pop(); int i2=i1+1;
seg1[i1%2].upd(i1,a[i1][1]-a[i1][2]);
seg1[i2%2].upd(i2,a[i2][1]-a[i2][2]);
idx.pb({i1,i2});
}
while (!pq2.empty() && pq2.top().first<=d) {
auto [dif,i1]=pq2.top(); pq2.pop();
seg2[i1%2].upd(i1+1,a[i1+1][1]-a[i1+1][2]);
}
for (auto [i1,i2]:idx) uf.mg(i1,i2);
ret[qi]=ans;
}
return ret;
}
