#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
const int M = 1e5 + 1, inf = 1e9 + 1;
int w[M], a[M], b[M], col[M], sz[M], mn[M][4];
ll su[M];
vector<int> ver[M];
void add(int u,int v)
{
u=col[u], v=col[v];
if (u==v) return;
if (sz[u]<sz[v]) swap(u,v);
for (int i:ver[v])
col[i]=u, ver[u].push_back(i);
ver[v].clear();
sz[u]+=sz[v],su[u]+=su[v];
for (int j=0;j<4;j++)
mn[u][j]=min(mn[u][j],mn[v][j]);
}
ll cal(int i)
{
i=col[i];
return su[i]+min(mn[i][mn[i][3]%2],mn[i][2])*(sz[i]%2);
}
vector<ll> calculate_costs(vector<int> W, vector<int> A,
vector<int> B, vector<int> E)
{
int n=W.size(), q=E.size();
vector<pair<int,int>> v,v1;
for (int i=0;i<n;i++)
v.push_back({W[i],i});
for (int i=0;i<q;i++)
v1.push_back({E[i],i});
sort(all(v)), sort(all(v1));
vector<pair<int,pair<int,int>>> edg;
ll cur=0;
vector<ll> ans(q);
for (int i=0;i<n;i++)
{
w[i]=v[i].first,b[i]=B[v[i].second],a[i]=A[v[i].second]-b[i];
if (i) edg.push_back({w[i]-w[i-1],{i-1,i}});
if (i>1) edg.push_back({w[i]-w[i-2],{i-2,i}});
col[i]=mn[i][3]=i,sz[i]=1,ver[i]={i},su[i]=b[i];
mn[i][0]=mn[i][1]=mn[i][2]=inf;
mn[i][i%2]=a[i];
cur+=cal(i);
}
sort(all(edg));
int id=0;
for (int i=0;i<q;i++)
{
int x=v1[i].first;
while (id<edg.size() && edg[id].first<=x)
{
pair<int,int> ed=edg[id++].second;
if (ed.first==ed.second-1)
{
cur-=cal(ed.first)+cal(ed.second);
add(ed.first,ed.second);
cur+=cal(ed.first);
}
else
{
cur-=cal(ed.first);
mn[col[ed.first]][2]=min(mn[col[ed.first]][2],a[ed.first+1]);
cur+=cal(ed.first);
}
}
ans[v1[i].second]=cur;
}
return ans;
}
