#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define inf 1000000000000
vi parent;
vi le;
vi oddMin, evenMin, sureMin, cnt;
ll ans = 0;
void init(ll n, vp point){
parent.clear(); le.clear(); cnt.clear(); sureMin.clear(); oddMin.clear(); evenMin.clear();
parent.resize(n);
le.resize(n, 0);
cnt.resize(n, 1);
oddMin.resize(n, inf);
evenMin.resize(n, inf);
sureMin.resize(n, inf);
for(int i = 0; i < n; i++){
parent[i] = i;
le[i] = point[i].first;
evenMin[i] = point[i].second;
}
}
ll find(ll u){
if(parent[u] != u) parent[u] = find(parent[u]);
return parent[u];
}
ll query(ll u){
u = find(u);
if(cnt[u] % 2 == 0) return 0;
return min(sureMin[u], evenMin[u]);
}
void merge(ll u, ll v){
ll ru = find(u);
ll rv = find(v);
if(ru == rv){
return;
}
if(le[ru] < le[rv]) swap(ru, rv);
ans -= (query(ru) + query(rv));
parent[ru] = rv;
sureMin[rv] = min(sureMin[rv], sureMin[ru]);
if(cnt[rv] % 2 == 0){
evenMin[rv] = min(evenMin[rv], evenMin[ru]);
oddMin[rv] = min(oddMin[rv], oddMin[ru]);
}else{
evenMin[rv] = min(evenMin[rv], oddMin[ru]);
oddMin[rv] = min(oddMin[rv], evenMin[ru]);
}
cnt[rv] += cnt[ru];
cnt[ru] = 0;
ans += query(rv);
}
std::vector<long long> calculate_costs(
std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E){
ll n = A.size();
vi C(n);
vp point(n);
ans = 0;
for(int i = 0; i < n; i++){
C[i] = A[i] - B[i];
ans += A[i];
point[i] = {W[i], C[i]};
}
set<ll> queries;
map<ll, ll> answer;
for(int i = 0; i < E.size(); i++){
queries.insert(E[i]);
}
set<pair<ll, pp>> event;
sort(begin(point), end(point));
init(n, point);
for(int i = 0; i < point.size(); i++){
if(i + 1 < point.size()) {
event.insert({point[i + 1].first - point[i].first, {1, i}}); //merging components
if(i > 0) event.insert({point[i + 1].first - point[i - 1].first, {-1, i}});
}
}
for(ll time : queries){
if(event.size() > 0){
while((event.size() > 0) && time >= (*event.begin()).first){
pair<ll, pp> akt = (*event.begin());
event.erase(event.begin());
if(akt.second.first == 1){
merge(akt.second.second, akt.second.second + 1);
}else{
ll u = akt.second.second;
ll ru = find(u);
ans -= query(ru);
sureMin[ru] = min(sureMin[ru], point[u].second);
ans += query(ru);
}
}
}
answer[time] = ans;
}
vi ANS(E.size());
for(int i = 0; i < E.size(); i++){
ANS[i] = answer[E[i]];
}
return ANS;
}
/*
int main(){
ll n;
cin >> n;
vector<int> W(n), A(n), B(n);
for(int i = 0; i < n; i++){
cin >> W[i] >> A[i] >> B[i];
}
ll q;
cin >> q;
vector<int> E(q);
for(int i = 0; i < q; i++){
cin >> E[i];
}
vi aaa = calculate_costs(W, A, B, E);
for(int i = 0; i < q; i++){
cout << aaa[i] << '\n';
}
}*/
