#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[100005];
int p[100005];
int sz[100005];
void make_set(int i)
{
p[i] =i;
sz[i] = 1;
}
int get_papa(int i)
{
if(p[i] == i)
return i;
return p[i] = get_papa(p[i]);
}
int ans = 0;
void union_set(int a, int b)
{
a = get_papa(a);
b = get_papa(b);
if(a == b)return;
if(sz[a] > sz[b])swap(a, b);
if(sz[a] % 2 && sz[b] % 2)
ans++;
p[a] = b;
sz[b]+= a;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A,
vector<int> B, vector<int> E) {
int Q = (int)E.size();
vector<long long> R;
vector<pair<int, pair<int, int>>> qaq;
for (int i = 0; i < A.size(); i++)
{
qaq.push_back({W[i], {A[i], B[i]}});
}
sort(qaq.begin(), qaq.end());
for (int i = 0; i < A.size(); i++)
{
W[i] = qaq[i].first;
A[i] = qaq[i].second.first;
B[i] = qaq[i].second.second;
make_set(i);
}
vector<pair<int ,int>> zuyg;
for (int i = 0; i < W.size() - 1; i++)
{
zuyg.push_back({W[i + 1] - W[i], i});
}
sort(zuyg.begin(), zuyg.end());
vector<pair<int, int>> sq;
for (int i = 0; i < E.size(); i++)
{
sq.push_back({E[i], i});
}
sort(sq.begin(), sq.end());
int ind = 0;
vector<pair<int, int>> hogna;
for(auto g: sq)
{
while (ind < zuyg.size() && zuyg[ind].first <= g.first)
{
union_set(zuyg[ind].second, zuyg[ind].second + 1);
ind++;
}
hogna.push_back({g.second, 2 * (A.size() - ans)});
}
sort(hogna.begin(), hogna.end());
for (int i = 0; i < hogna.size(); i++)
{
R.push_back(hogna[i].second);
}
return R;
}
