#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
const ll INF = 1e17;
ll n, q;
vc<ll> w, a, b, ques, res;
ll ans = 0;
vc<ll> sum, par, be, beg, bo, bog;
set<ll> seg;
struct Event {
ll d, t, i;
};
vc<Event> events;
void sortItems() {
vc<ll> ord(n);
iota(all(ord), 0);
sort(all(ord), [&](ll i, ll j) {
return w[i] < w[j];
});
vc<ll> tmp(n);
for (ll i = 0; i < n; i++)
tmp[i] = w[ord[i]];
swap(tmp, w);
for (ll i = 0; i < n; i++)
tmp[i] = a[ord[i]];
swap(tmp, a);
for (ll i = 0; i < n; i++)
tmp[i] = b[ord[i]];
swap(tmp, b);
}
ll total(ll i) {
if (par[i] == 0)
return sum[i];
else
return sum[i] + min(be[i], bog[i]);
}
void init() {
sum = b;
par.assign(n, 1);
be.resize(n);
for (ll i = 0; i < n; i++)
be[i] = a[i] - b[i];
beg.assign(n, INF);
bo = bog = beg;
for (ll i = 0; i <= n; i++)
seg.insert(i);
ans = 0;
for (ll i = 0; i < n; i++)
ans += total(i);
res.resize(q);
}
void merge(ll i) {
ll x = *(--seg.upper_bound(i));
ll y = i + 1;
ans -= total(x) + total(y);
sum[x] += sum[y];
if (par[x] == 0) {
be[x] = min(be[x], be[y]);
beg[x] = min(beg[x], beg[y]);
bo[x] = min(bo[x], bo[y]);
bog[x] = min(bog[x], bog[y]);
} else {
be[x] = min(be[x], bo[y]);
beg[x] = min(beg[x], bog[y]);
bo[x] = min(bo[x], be[y]);
bog[x] = min(bog[x], beg[y]);
}
par[x] ^= par[y];
ans += total(x);
seg.erase(i + 1);
}
void makeGood(ll i) {
ll l = *(--seg.upper_bound(i));
ans -= total(l);
if ((i - l) % 2 == 0)
beg[l] = min(beg[l], a[i] - b[i]);
else
bog[l] = min(bog[l], a[i] - b[i]);
ans += total(l);
}
void handle(Event &event) {
if (event.t == 0)
merge(event.i);
else if (event.t == 1)
makeGood(event.i);
else
res[event.i] = ans;
}
void sweep() {
events.reserve(n - 1 + n - 2 + q);
for (ll i = 0; i + 1 < n; i++)
events.pub({w[i + 1] - w[i], 0, i});
for (ll i = 0; i + 2 < n; i++)
events.pub({w[i + 2] - w[i], 1, i + 1});
for (ll i = 0; i < q; i++)
events.pub({ques[i], 2, i});
sort(all(events), [&](auto &x, auto &y) {
if (x.d != y.d)
return x.d < y.d;
if (x.t != y.t)
return x.t < y.t;
return x.i < y.i;
});
for (auto &event : events)
handle(event);
}
void program() {
sortItems();
init();
sweep();
}
vc<ll> calculate_costs(vc<int> W, vc<int> A, vc<int> B, vc<int> E) {
n = sz(W);
q = sz(E);
w.assign(all(W));
a.assign(all(A));
b.assign(all(B));
ques.assign(all(E));
program();
return res;
}
