// testing the matrix
#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;
st merge(st l, st r, int tm) {
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], min({l[i][0], l[i][1], l[i][2]}) + min({r[0][j], r[1][j], r[2][j]}));
}
}
if (!can1[X[tm]]) return re;
ll dif = B[X[tm]] + B[X[tm+1]] - A[X[tm]] - A[X[tm+1]];
chmin(re[0][0], l[0][1] + r[1][0] + dif);
chmin(re[0][1], l[0][1] + r[1][1] + dif);
chmin(re[1][0], l[1][1] + r[1][0] + dif);
chmin(re[1][1], l[1][1] + r[1][1] + dif);
return re;
}
void update(int p, int tl = 0, int tr = N-1, int i = 1) {
if (tl == tr) {
ll v = A[X[tl]];
tree[i] = { {{v,v,v}, {v,INF,INF}, {v,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], 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), can1.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) {
can1[X[dist.back().second]] = true;
update(dist.back().second);
dist.pop_back();
}
res[Y[j]] = tree[1][0][0];
}
return res;
}
