#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
void buildls(ll l, ll r, ll i, vl& tree, ll p, vl& vals){
if (l == r && l < vals.size() && l%2 == p){
tree[i] = vals[l];
return;
}
else if (l == r){return;}
ll mid = (l+r)/2;
buildls(l, mid, 2*i, tree, p, vals);
buildls(mid +1, r, 2*i+1, tree, p, vals);
tree[i] = min(tree[2*i], tree[2*i+1]);
return;
}
void buildg(ll l, ll r, ll i, vl& tree, vl& vals){
if (l == r && l < vals.size()){
tree[i] = vals[l];
return;
}
else if (l == r){return;}
ll mid = (l+r)/2;
buildg(l, mid, 2*i, tree, vals);
buildg(mid +1, r, 2*i+1, tree, vals);
tree[i] = min(tree[2*i], tree[2*i+1]);
return;
}
void update(ll l, ll r, vl& tree, ll i, ll c, ll pos){
if (l == r && l == pos){
tree[i] = c;
return;
}
if (r < pos || l > pos){
return;
}
ll mid = (l+r)/2;
update(l, mid, tree, 2*i, c, pos);
update(mid+1,r,tree,2*i+1, c, pos);
tree[i] = min(tree[2*i], tree[2*i+1]);
return;
}
ll query(ll l, ll r, ll L, ll R, ll i, vl& tree){
if (L <= l && r <= R){
return tree[i];
}
if (r < L || R < l){
return 1e10;
}
ll mid = (l+r)/2;
ll a = query(l, mid, L, R, 2*i, tree);
ll b = query(mid+1, r, L, R, 2*i+1, tree);
return min(a,b);
}
std::vector<long long> calculate_costs(
std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E){
ll n = W.size();
vll nums;
for (ll i = 0; i < n; i++){
nums.push_back({W[i], A[i], B[i]});
}
sort(nums.begin(), nums.end());
vector<pl> queries;
for (ll i = 0; i < E.size(); i++){
queries.push_back({E[i], i});
}
sort(queries.begin(), queries.end());
reverse(queries.begin(), queries.end());
// Intervals
set<ll> b;
b.insert(0);
vector<pl> intervals (n, {-1,0});
// Events
vector<pl> gaps;
for (ll i = 0; i < n-1; i++){
gaps.push_back({nums[i+1][0]-nums[i][0], i});
}
sort(gaps.begin(), gaps.end()); reverse(gaps.begin(), gaps.end()); gaps.push_back({-1,0});
vector<pl> spojky;
for (ll i = 1; i < n-1; i++){
spojky.push_back({nums[i+1][0]-nums[i-1][0], i});
}
sort(spojky.begin(), spojky.end()); reverse(spojky.begin(), spojky.end()); spojky.push_back({-1,0});
// Precalc
vl dif(n);
for (ll i = 0; i < n; i++){dif[i] = nums[i][1]-nums[i][2];}
// Tree handeling
vl treel (4*n+4, 1e10);
vl trees (4*n + 4, 1e10);
vl treeg (4*n+4, 1e10);
ll N = 1;
while (N < n){ N *= 2;}
buildls(0,N-1,1,treel,1, dif);//parity
buildls(0,N-1,1,trees,0, dif);
buildg(0,N-1,1,treeg, dif);
vl prefix (n+1,0);
for (ll i = 0; i < n; i++){
prefix[i+1] = prefix[i] + nums[i][2];
}
ll suma = prefix[n] - prefix[0] + query(0,N-1,0,n-1,1,treeg); // (i, j) = [j+1] - [i]
intervals[0] = {n-1, suma};
vl ans(queries.size(), 0);
// interval calc
auto intcalc = [&](ll zacatek, ll konec) {
ll sub = prefix[konec+1]-prefix[zacatek];
if ((konec - zacatek)%2 == 0){ // odd length is a problem, but bounds are including
ll a, b;
b = 1e10;
if (zacatek % 2 == 0){
a = query(0, N-1, zacatek, konec, 1, trees);
}
else{
a = query(0, N-1, zacatek, konec, 1, treel);
}
if (zacatek + 1 <= konec - 1){
b = query(0, N-1, zacatek+1, konec-1, 1, treeg);
}
sub += min(a,b);
}
return sub;
};
// main algorithm
ll p1 = 0; ll p2 = 0;
for (ll i = 0; i < queries.size(); i++){
// Handle updates of spojky deleting, interval destruction, by gaps
ll k = queries[i].first;
while (spojky[p1].first > k || gaps[p2].first > k){
if (spojky[p1].first >= gaps[p2].first){
//Recalc interval where spojka is
ll pos = spojky[p1].second;
update(0, N-1, treeg, 1, 1e10, pos);
ll start = *prev(b.upper_bound(pos));
ll end = intervals[start].first;
suma -= intervals[start].second;
ll sub = intcalc(start, end);
suma += sub;
intervals[start].second = sub;
p1++;
}
else{
ll end1 = gaps[p2].second; //position of last element of first interval
ll start1 = *prev(b.upper_bound(end1));
ll end2 = intervals[start1].first;
ll start2 = end1 + 1;
suma -= intervals[start1].second;
ll sub = intcalc(start1, end1);
intervals[start1] = {end1, sub};
suma += sub;
sub = intcalc(start2, end2);
intervals[start2] = {end2, sub};
b.insert(start2);
suma += sub;
p2++;
}
}
ans[queries[i].second] = suma;
}
return ans;
}
/*/int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> W, A, B, E;
W = {15, 12, 2, 10, 21};
A = {5, 4, 5, 6, 3};
B = {1, 2, 2, 3, 2};
E = {5, 9, 1};
vl x = calculate_costs(W, A, B, E);
for (auto p : x){
cout << p << "\n";
}
return 0;
}/*/
