#include "nile.h"
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
using st = array<ll, 4>; // D D, D U, U D, U U U = unpaired D = done (paired or single)
#define def (st){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> can;
st merge(st l, st r, int tm) {
if (l == def) return r;
if (r == def) return l;
st re;
re[0] = min(l[0], l[1]) + min(r[0], r[2]);
re[1] = min(l[0], l[1]) + min(r[1], r[3]);
re[2] = min(l[2], l[3]) + min(r[0], r[2]);
re[3] = min(l[2], l[3]) + min(r[1], r[3]);
if (can[X[tm]]) {
ll dif = B[X[tm]] + B[X[tm+1]] - A[X[tm]] - A[X[tm+1]];
chmin(re[0], l[1] + r[2] + dif);
chmin(re[1], l[1] + r[3] + dif);
chmin(re[2], l[3] + r[2] + dif);
chmin(re[3], l[3] + r[3] + dif);
}
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]], A[X[tl]], 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], tm);
}
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), can.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>> dist;
for(int i = 0; i < N-1; i++) dist.push_back({W[X[i+1]]-W[X[i]], i});
sort(dist.begin(), dist.end(), greater<>());
vector<ll> res(Q);
for(int j = 0; j < Q; j++) {
while(dist.size() && E[Y[j]] >= dist.back().first) {
can[X[dist.back().second]] = true;
update(dist.back().second);
dist.pop_back();
}
res[Y[j]] = min({tree[1][0], tree[1][1], tree[1][2], tree[1][2]});
}
return res;
}
