#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<18;
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;
}
long long qq(int a, int l, int r, int lq, int rq, vector<long long> &s) {
if (l >= lq && r <= rq) return s[a];
int m = (l+r)/2;
long long p = 1000000000LL;
if (m > lq) p = min(p, qq(a<<1, l, m, lq, rq, s));
if (m < rq) p = min(p, qq(a<<1|1, m, r, lq, rq, s));
return p;
}
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<long long> mn(N, 1000000000LL); //pari, dispari, ci sono solo quelli centrali 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> sp(maxn<<1, 1000000000LL), sd(maxn<<1, 1000000000LL);
for (int i = 0; i < N; i+=2) sp[i+maxn] = stt[i][2];
for (int i = 1; i < N; i+=2) sd[i+maxn] = stt[i][2];
for (int i = maxn-1; i > 0; i--) {
sp[i] = min(sp[i<<1], sp[i<<1|1]);
sd[i] = min(sd[i<<1], sd[i<<1|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], mn[b]);
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 md;
if (infn[b][0] % 2) md = qq(1, 0, maxn, infn[b][0], infn[b][1], sd);
else md = qq(1, 0, maxn, infn[b][0], infn[b][1], sp);
s[b] += min(mn[b], md);
}
sum += s[b];
unite(a, b);
}
else if (att[1] == 2) {
int r = fr(att[2]+1);
sum -= s[r];
mn[r] = min(mn[r], 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 md;
if (infn[r][0] % 2) md = qq(1, 0, maxn, infn[r][0], infn[r][1], sd);
else md = qq(1, 0, maxn, infn[r][0], infn[r][1], sp);
s[r] += min(mn[r], md);
}
sum += s[r];
}
else ris[att[2]] = sum;
}
return ris;
}
