#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "";
int n;
ll sum=0,cur=0;
vector<pair<int,pair<int,int>>> v;
vector<ll> rs;
struct Artifact{
ll w,a,b,pos,val;
bool operator<(const Artifact& a) const{
return w<a.w;
}
}a[MAXN];
struct DSU{
int par[MAXN],sz[MAXN];
ll sum[MAXN],val[MAXN],MIN[MAXN][3];
void init(int n){
memset(MIN,0x3f,sizeof(MIN));
for(int i = 1; i<=n; ++i)
par[i]=i, sz[i]=1, sum[i]=a[i].val, MIN[i][i&1]=a[i].val;
}
int Find(int u){
if(u==par[u]) return u;
return par[u]=Find(par[u]);
}
void Union(int x, int y){
x=Find(x), y=Find(y);
if(x==y) return;
cur-=val[x], cur-=val[y];
if(x>y) swap(x,y);
if(sz[x]>1) MIN[x][2]=min(MIN[x][2],a[y].val+a[y-1].val+a[y-2].val);
if(sz[y]>1) MIN[x][2]=min(MIN[x][2],a[y].val+a[y+1].val+a[y-1].val);
par[y]=x, sz[x]+=sz[y], sum[x]+=sum[y];
for(int i = 0; i<3; ++i)
MIN[x][i]=min(MIN[x][i],MIN[y][i]);
if(sz[x]&1) val[x]=max(sum[x]-MIN[x][2],sum[x]-MIN[x][x&1]);
else val[x]=sum[x];
cur+=val[x];
}
}dsu;
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
rs.resize(sz(E));
n=sz(W);
for(int i = 1; i<=n; ++i)
sum+=A[i-1], a[i].w=W[i-1], a[i].a=A[i-1], a[i].b=B[i-1], a[i].val=A[i-1]-B[i-1];
for(int i = 0; i<sz(E); ++i)
v.pb(E[i],mp(2,i));
sort(a+1,a+n+1);
for(int i = 2; i<=n; ++i){
v.pb(a[i].w-a[i-1].w,mp(0,i));
if(i<n) v.pb(a[i+1].w-a[i-1].w,mp(1,i));
}
sort(v.begin(),v.end());
dsu.init(n);
for(pair<int,pair<int,int>>& p : v){
if(p.se.fi==0){
int x=p.se.se;
dsu.Union(x,x-1);
}else if(p.se.fi==1){
int x=dsu.Find(p.se.se),y=p.se.se;
cur-=dsu.val[x], dsu.MIN[x][2]=min(dsu.MIN[x][2],a[y].val);
dsu.val[x]=max(dsu.val[x],dsu.sum[x]-dsu.MIN[x][2]);
cur+=dsu.val[x];
}else rs[p.se.se]=sum-cur;
}
return rs;
}
//int main()
//{
// tt;
// if(fopen((NAME + ".INP").c_str(), "r")) fo;
// int n,q;
// cin >> n;
// vector<int> w(n),a(n),b(n);
// for(int i = 0; i<n; ++i)
// cin >> w[i] >> a[i] >> b[i];
// cin >> q;
// vector<int> e(q);
// for(int i = 0; i<q; ++i)
// cin >> e[i];
// vector<ll> rs=calculate_costs(w,a,b,e);
// for(ll& x : rs) cout << x << "\n";
//}
