#include "nile.h"
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;////////////////////////////////
using st = array<array<ll, 3>, 3>; // row = left, col = right
const st def = { {{INF, INF, INF}, {INF, INF, INF}, {INF, INF, INF}} };
inline void chmin(ll &x, ll y) {x = min(x,y);}
int N, D;
vector<ll> X, W, A, B;
vector<st> tree;
vector<bool> can1, can2;
void print(st &x) {
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
cout << x[i][j] << " \n"[j == 2];
}
}
}
st merge(st l, st r, int tl, int tm, int tr) {
if (l == def) return r;
if (r == def) return l;
st re = def;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
chmin(re[i][j], l[i][0] + r[0][j]);
}
}
if (can1[X[tm]]) {
ll dif = B[X[tm]] + B[X[tm+1]] - A[X[tm]] - A[X[tm+1]];
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
chmin(re[i][j], l[i][1] + r[1][j] + dif);
}
}
}
if (tm+2 <= tr && can2[X[tm]]) {
ll dif = B[X[tm]] + B[X[tm+2]] - A[X[tm]] - A[X[tm+2]];
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
chmin(re[i][j], l[i][1] + r[2][j] + dif);
}
}
}
if (tm-1 >= tl && can2[X[tm-1]]) {
ll dif = B[X[tm-1]] + B[X[tm+1]] - A[X[tm-1]] - A[X[tm+1]];
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
chmin(re[i][j], l[i][2] + r[1][j] + dif);
}
}
}
if (tr-tl+1 == 2) {
re[0][2] = re[2][0] = A[X[tl]] + A[X[tr]];
}
if (tr-tl+1 == 3) {
re[0][2] = re[2][0] = re[1][2] = re[2][1] = A[X[tl]] + A[X[tm]] + A[X[tr]];
}
// cout << tl << ' ' << tr << endl;
// print(re);
return re;
}
void update(int p, int tl = 0, int tr = N-1, int i = 1) {
if (tl == tr) {
tree[i] = { {{A[X[tl]], A[X[tl]], INF}, {A[X[tl]], INF, INF}, {INF, INF, INF}} };
return ;
}
int tm = (tl + tr) / 2;
if (p <= tm) update(p, tl, tm, i * 2);
else update(p, tm + 1, tr, i * 2 + 1);
tree[i] = merge(tree[i * 2], tree[i * 2 + 1], tl, tm, tr);
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
N = W.size(); int Q = E.size();
::W.resize(N), ::A.resize(N), ::B.resize(N), can1.resize(N), can2.resize(N), X.resize(N);
for(int i = 0; i < N; i++) ::W[i] = W[i], ::A[i] = A[i], ::B[i] = B[i];
iota(X.begin(), X.end(), 0);
sort(X.begin(), X.end(), [&](const int a, const int b) {return W[a] < W[b];} );
vector<int> Y(Q);
iota(Y.begin(), Y.end(), 0);
sort(Y.begin(), Y.end(), [&](const int a, const int b) {return E[a] < E[b];} );
tree.resize(N*4, def);
for(int i = 0; i < N; i++) update(i);
vector<pair<ll,int>> dist1, dist2;
for(int i = 0; i < N-1; i++) dist1.push_back({W[X[i+1]]-W[X[i]], i});
for(int i = 0; i < N-2; i++) dist2.push_back({W[X[i+2]]-W[X[i]], i});
sort(dist1.begin(), dist1.end(), greater<>());
sort(dist2.begin(), dist2.end(), greater<>());
vector<ll> res(Q);
for(int j = 0; j < Q; j++) {
while(dist1.size() && E[Y[j]] >= dist1.back().first) {
can1[X[dist1.back().second]] = true;
update(dist1.back().second);
dist1.pop_back();
}
while(dist2.size() && E[Y[j]] >= dist2.back().first) {
can2[X[dist2.back().second]] = true;
update(dist2.back().second);
dist2.pop_back();
}
res[Y[j]] = tree[1][0][0];
}
return res;
}
