#include<bits/stdc++.h>
//#include<bits/extc++.h>
#include "nile.h"
#define fi first
#define se second
#define int long long
using namespace std;
//using namespace __gnu_pbds;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{
int a; int b; int w;
};
bool cmp(node q, node z){
return q.w<z.w;
}
struct querys{
int d; int idx;
};
bool cmpq(querys a, querys b){
return a.d<b.d;
}
const int MAXN=3;
struct Matrix{
int mat[3+1][3+1]; int h=3; int w=3; //int h,w;
Matrix(){
memset(mat,0,sizeof(mat));
}
void build(){
for(int i=1; i<=3; i++){
for(int j=1; j<=3; j++){
mat[i][j]=1e18;
}
}
}
};
Matrix operator*(const Matrix &a, const Matrix &b){
Matrix c; c.build(); //c.h=a.w; c.w=b.w;
for(int i=1; i<=a.h; i++){
for(int j=1; j<=b.w; j++){
for(int k=1; k<=a.w; k++){
c.mat[i][j]=min(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);
}
}
}
return c;
};
const int maxn=1e5+10; Matrix sum[maxn<<2]; Matrix d; int f1; int f2;
void build(int l, int r, int rt, const vector<node>&v){
if(l==r){
sum[rt].build(); sum[rt].mat[1][1]=v[l].a; sum[rt].mat[2][1]=0; sum[rt].mat[3][2]=0; return;
}
int mid=(l+r)>>1; build(l,mid,rt<<1,v); build(mid+1,r,rt<<1|1,v);
sum[rt]=sum[rt<<1|1]*sum[rt<<1];
}
void update(int l, int r, int rt, int idx){
if(l==r){
if(l==2){
sum[rt].mat[1][1]=f2; sum[rt].mat[2][1]=f1; sum[rt].mat[3][1]=0; return;
}
sum[rt]=d; return;
}
int mid=(l+r)>>1;
if(idx<=mid)update(l,mid,rt<<1,idx); else update(mid+1,r,rt<<1|1,idx);
if(l==1 && r==2)sum[rt]=sum[rt<<1|1]; else sum[rt]=sum[rt<<1|1]*sum[rt<<1];
}
vector<int>calculate_costs(vector<int32_t>W, vector<int32_t>A, vector<int32_t>B, vector<int32_t>E){
int n=W.size(); int q=E.size(); vector<node>v(n+1); vector<querys>qry(q);
for(int i=1; i<=n; i++){
v[i].a=A[i-1]; v[i].b=B[i-1]; v[i].w=W[i-1];
}
sort(v.begin()+1,v.end(),cmp); vector<pair<int,int>>v1; vector<pair<int,int>>v2;
for(int i=2; i<=n; i++){
v1.push_back({v[i].w-v[i-1].w,i});
if(i>=3)v2.push_back({v[i].w-v[i-2].w,i});
}
for(int i=0; i<q; i++){
qry[i].d=E[i]; qry[i].idx=i;
}
sort(qry.begin(),qry.end(),cmpq); vector<int>ans(q); build(1,n,1,v);
sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); int x=0; int y=0;
for(int i=0; i<q; i++){
f1=v[1].a; if(v[2].w-v[1].w<=qry[i].d)f2=v[1].b+v[2].b; else f2=v[2].a+v[1].a;
update(1,n,1,2); d.build(); d.mat[2][1]=0; d.mat[3][2]=0;
while(x<v1.size() && v1[x].fi<=qry[i].d){
int idx=v1[x].se; d.mat[1][1]=v[idx].a; d.mat[1][2]=v[idx].b+v[idx-1].b; x++; update(1,n,1,idx);
}
while(y<v2.size() && v2[y].fi<=qry[i].d){
int idx=v2[y].se; d.mat[1][1]=v[idx].a; d.mat[1][2]=v[idx].b+v[idx-1].b;
d.mat[1][3]=v[idx].b+v[idx-1].a+v[idx-2].b; y++; update(1,n,1,idx);
}
ans[qry[i].idx]=sum[1].mat[1][1];
}
return ans;
}
