// #include "nile.cpp"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
// #define int long long
// #define int unsigned long long
// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>
void open_file(string filename) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
// const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 1e5 + 25;
vector<pii> v; ll cst = 0;
int par[maxN], sz[maxN], mn[maxN][3];
int get(int x) {
if (sz[x] % 2 == 0) return 0;
return min(mn[x][x % 2], mn[x][2]);
}
void make_set(int n) {
for (int i = 0; i < n; i++) {
mn[i][0] = mn[i][1] = mn[i][2] = inf;
mn[i][i % 2] = v[i].sc; par[i] = i; sz[i] = 1;
cst += get(i);
}
}
int find_set(int x) {
if (par[x] == x)
return x;
return par[x] = find_set(par[x]);
}
void union_type_1(int x, int y) {
x = find_set(x);
y = find_set(y);
if (x > y) swap(x, y);
cst -= get(x); cst -= get(y);
par[y] = x; sz[x] += sz[y];
for (int i = 0; i < 3; i++)
mn[x][i] = min(mn[x][i], mn[y][i]);
cst += get(x);
}
void union_type_2(int x) {
int val = v[x].sc;
x = find_set(x);
cst -= get(x);
mn[x][2] = min(mn[x][2], val);
cst += get(x);
}
vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int n = w.size(), m = e.size();
for (int i : b) cst += i;
for (int i = 0; i < n; i++)
v.pb({w[i], a[i] - b[i]});
vector<ll> ans(m);
sort(all(v)); make_set(n);
vector<pair<int, pii>> events;
for (int i = 1; i < n; i++) {
events.pb({v[i].ff - v[i - 1].ff, {1, i}});
if (i + 1 < n) events.pb({v[i + 1].ff - v[i - 1].ff, {2, i}});
} for (int i = 0; i < m; i++)
events.pb({e[i], {3, i}});
sort(all(events));
for (auto i : events) {
if (i.sc.ff == 1)
union_type_1(i.sc.sc - 1, i.sc.sc);
else if (i.sc.ff == 2)
union_type_2(i.sc.sc);
else ans[i.sc.sc] = cst;
} return ans;
}
// int main() {
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<int> W(N), A(N), B(N);
// for (int i = 0; i < N; i++)
// assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
// int Q;
// assert(1 == scanf("%d", &Q));
// std::vector<int> E(Q);
// for (int j = 0; j < Q; j++)
// assert(1 == scanf("%d", &E[j]));
// fclose(stdin);
// std::vector<long long> R = calculate_costs(W, A, B, E);
// int S = (int)R.size();
// for (int j = 0; j < S; j++)
// printf("%lld\n", R[j]);
// fclose(stdout);
// return 0;
// }
