#include "nile.h"
#include <vector>
#include <algorithm>
using namespace std;
const int DIM = 1e5;
const long long INF = 1e16;
struct event
{
long long val;
int pos, ch;
};
vector <event> ev;
struct elem
{
long long w, a, b;
};
elem v[DIM + 1];
vector <long long> sol;
struct DSU
{
int t[DIM + 1], sz[DIM + 1];
long long dlt[DIM + 1][2], dlt2[DIM + 1][2]; ///0 -> impar, 1 -> par
long long sol;
void init (int n)
{
for (int i = 0; i < n; i++)
{
t[i] = i;
sz[i] = 1;
dlt[i][0] = v[i].a - v[i].b;
dlt[i][1] = dlt2[i][0] = dlt2[i][1] = INF;
sol += v[i].a;
}
}
int rad (int x)
{
if (x == t[x])
return x;
return t[x] = rad (t[x]);
}
void reun (int x, int y)
{
if (x > y)
swap (x, y);
x = rad (x), y = rad (y);
t[y] = x;
if (sz[y] % 2 != 0)
sol -= min (dlt[y][0], dlt2[y][1]);
if (sz[x] % 2 != 0)
sol -= min (dlt[x][0], dlt2[x][1]);
if (sz[x] % 2 != 0)
{
swap (dlt[y][0], dlt[y][1]);
swap (dlt2[y][0], dlt2[y][1]);
}
for (int i = 0; i < 2; i++)
{
dlt[x][i] = min (dlt[x][i], dlt[y][i]);
dlt2[x][i] = min (dlt2[x][i], dlt2[y][i]);
}
sz[x] += sz[y];
if (sz[x] % 2 != 0)
sol += min (dlt[x][0], dlt2[x][1]);
}
void update (int pos, long long d)
{
int x = rad (pos);
if (sz[x] % 2 != 0)
sol -= min (dlt[x][0], dlt2[x][1]);
if ((pos - x + 1) % 2 == 0)
dlt2[x][1] = min (dlt2[x][1], d);
else
dlt2[x][0] = min (dlt2[x][0], d);
if (sz[x] % 2 != 0)
sol += min (dlt[x][0], dlt2[x][1]);
}
long long get_sol ()
{
return sol;
}
};
DSU dsu;
bool cmp (event a, event b)
{
if (a.val == b.val)
return a.ch < b.ch;
return a.val < b.val;
}
bool cmpv (elem a, elem b)
{
return a.w < b.w;
}
void get_events (int n)
{
for (int i = 0; i < n - 1; i++)
ev.push_back ({v[i + 1].w - v[i].w, i, 1});
for (int i = 1; i < n - 1; i++)
ev.push_back ({v[i + 1].w - v[i - 1].w, i, 2});
sort (ev.begin (), ev.end (), cmp);
}
void solve ()
{
for (int i = 0; i < (int) ev.size (); i++)
{
int ch = ev[i].ch, pos = ev[i].pos;
if (ch == 1)
{
dsu.reun (pos, pos + 1);
}
else if (ch == 2)
{
dsu.update (pos, v[pos].a - v[pos].b);
}
else if (ch == 3)
sol[pos] = dsu.get_sol ();
}
}
std::vector<long long> calculate_costs (std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> Q)
{
int n = (int) W.size ();
for (int i = 0; i < n; i++)
v[i] = {W[i], A[i], B[i]};
sort (v, v + n, cmpv);
dsu.init (n);
int q = (int) Q.size ();
sol.resize (q);
for (int i = 0; i < q; i++)
ev.push_back ({Q[i], i, 3});
get_events (n);
solve ();
return sol;
}
