#include <bits/stdc++.h>
using namespace std;
// #include "grader.cpp"
#define NL '\n'
#define EL cout << NL
#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i < (n); i++)
#define PRINTV(v) for (auto a:v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a:v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;
vvl trees(2);
ll update(vl& tree, ll k, ll x, ll l, ll r, ll i) {
if (k < l || r <= k) return tree[i];
if (l+1 >= r) return tree[i] = x;
ll m = (l+r)/2;
return tree[i] = min(update(tree,k,x,l,m,2*i+1),update(tree,k,x,m,r,2*i+2));
}
ll query(vl& tree, ll ql, ll qr, ll l, ll r, ll i) {
if (ql <= l && r <= qr) return tree[i];
if (r <= ql || qr <= l) return 1e18;
ll m = (l+r)/2;
return min(query(tree,ql,qr,l,m,2*i+1),query(tree,ql,qr,m,r,2*i+2));
}
vl dsu;
vl l;
vl r;
ll n;
ll find(ll u) {
if (dsu[u] == u) return u;
else return dsu[u] = find(dsu[u]);
}
void unite(ll x, ll y) {
ll a = find(x);
ll b = find(y);
dsu[b] = a;
l[a] = min(l[a],l[b]);
r[a] = max(r[a],r[b]);
}
ll get_ans(ll x) {
ll a = find(x);
if ((l[a] % 2) != (r[a] % 2)) return 0;
return query(trees[l[a]%2],l[a],r[a]+1,0,n,0);
}
std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a, std::vector<int> b, std::vector<int> e) {
int q = (ll)e.size();
n = w.size();
vpl tosort;
FOR(i,n) tosort.push_back({w[i],i});
sort(all(tosort));
vl x(n);
FOR(i,n) x[i] = tosort[i].f;
vl c(n);
ll bsum = 0;
ll cur = 0;
FOR(i,n) {
bsum += b[i];
ll j = tosort[i].s;
c[i] = a[j]-b[j];
cur += c[i];
}
trees[0].resize(4*n);
trees[1].resize(4*n);
FOR(i,n) {
update(trees[i%2],i,c[i],0,n,0);
update(trees[(i+1)%2],i,1e18,0,n,0);
}
set<ll> stuffhappens;
map<ll,vl> skips;
map<ll,vpl> joins;
map<ll,ll> queries;
for (auto k: e) queries[k] = 0;
FOR(i,n-1) {
joins[abs(x[i+1]-x[i])].push_back({i,i+1});
}
FORS(i,1,n-1) {
skips[abs(x[i+1]-x[i-1])].push_back(i);
}
dsu.resize(n);
l.resize(n);
r.resize(n);
FOR(i,n) dsu[i] = l[i] = r[i] = i;
for (auto [k,s]: skips) stuffhappens.insert(k);
for (auto [k,s]: joins) stuffhappens.insert(k);
for (auto [k,s]: queries) stuffhappens.insert(k);
for (auto d: stuffhappens) {
for (auto [a,b]: joins[d]) {
cur -= get_ans(a);
cur -= get_ans(b);
unite(a,b);
cur += get_ans(a);
}
for (auto i: skips[d]) {
cur -= get_ans(i);
update(trees[(i+1)%2],i,c[i],0,n,0);
cur += get_ans(i);
}
if (queries.count(d) > 0) {
queries[d] = cur;
}
}
vl ans(q);
FOR(i,q) ans[i] = queries[e[i]]+bsum;
return ans;
}
