#include <bits/stdc++.h>
using namespace std;
vector<int> par(1e6);
int fr(int a) {
if (a == par[a]) return a;
return par[a] = fr(par[a]);
}
void unite(int a, int b) {
if (fr(a) == fr(b)) return;
par[par[a]] = b;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = W.size();
vector<array<long long, 3>> stt(N);
for (int i = 0; i < N; i++) stt[i] = {W[i], B[i], A[i]-B[i]};
sort(stt.begin(), stt.end());
int Q = E.size();
par.resize(N); iota(par.begin(), par.end(), 0);
vector<array<long long, 3>> od;
for (int i = 0; i < Q; i++) od.push_back({E[i], 3, i});
for (int i = 0; i < N-1; i++) {
if (i < N-2) od.push_back({stt[i+2][0]-stt[i][0], 2, i});
od.push_back({stt[i+1][0]-stt[i][0], 1, i});
}
sort(od.begin(), od.end());
vector<array<long long, 2>> mn(N, {1000000000LL, 1000000000LL}); //pari, dispari, ci sono solo quelli centrsli i bordi sono a mano
vector<long long> s(N);
for (int i = 0; i < N; i++) {
s[i] = stt[i][1]+stt[i][2];
}
vector<array<long long, 2>> infn(N);
for (int i = 0; i < N; i++) infn[i][0] = i;
for (int i = 0; i < N; i++) infn[i][1] = i+1;
vector<long long> ris(Q);
long long sum = 0;
for (int i = 0; i < N; i++) sum += A[i];
vector<long long> pr(N+1, 0);
for (int i = 1; i <= N; i++) pr[i] = pr[i-1]+stt[i-1][1];
for (int k = 0; k < od.size(); k++) {
array<long long, 3> att = od[k];
if (att[1] == 1) {
long long a = fr(att[2]), b = fr(att[2]+1);
sum -= s[a]; sum -= s[b];
mn[b] = {min(mn[a][0], mn[b][0]), min(mn[a][1], mn[b][1])};
infn[b] = {min(infn[a][0], infn[b][0]), max(infn[a][1], infn[b][1])};
s[b] = pr[infn[b][1]]-pr[infn[b][0]];
if ((infn[b][1]-infn[b][0])%2) {
long long dt = 1000000000LL;
if (infn[b][0]%2) dt = mn[b][0];
else dt = mn[b][1];
dt = min(dt, min(stt[infn[b][0]][2], stt[infn[b][1]-1][2]));
s[b] += dt;
}
sum += s[b];
unite(a, b);
}
else if (att[1] == 2) {
int r = fr(att[2]+1);
sum -= s[r];
if (att[2]%2) mn[r][0] = min(mn[r][0], stt[att[2]+1][2]);
else mn[r][1] = min(mn[r][1], stt[att[2]+1][2]);
s[r] = pr[infn[r][1]]-pr[infn[r][0]];
if ((infn[r][1]-infn[r][0])%2) {
long long dt = 1000000000LL;
if (infn[r][0]%2) dt = mn[r][0];
else dt = mn[r][1];
dt = min(dt, min(stt[infn[r][0]][2], stt[infn[r][1]-1][2]));
s[r] += dt;
}
sum += s[r];
}
else ris[att[2]] = sum;
}
return ris;
}
