#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 1e5 + 5;
const ll inf = 1e18;
struct segtree {
ll st[4 * N];
void build(int x, int tl, int tr) {
if (tl == tr) st[x] = inf;
else {
int tm = (tl + tr) / 2;
build(2 * x, tl, tm);
build(2 * x + 1, tm + 1, tr);
st[x] = inf;
}
}
void update(int x, int tl, int tr, int i, ll val) {
if (tl == tr) st[x] = val;
else {
int tm = (tl + tr) / 2;
if (i <= tm) update(2 * x, tl, tm, i, val);
else update(2 * x + 1, tm + 1, tr, i, val);
st[x] = min(st[2 * x], st[2 * x + 1]);
}
}
ll get(int x, int tl, int tr, int l, int r) {
if (tr < l or r < tl) return inf;
if (l <= tl and tr <= r) return st[x];
int tm = (tl + tr) / 2;
return min(get(2 * x, tl, tm, l, r), get(2 * x + 1, tm + 1, tr, l, r));
}
} st1, st2;
ll par[N], sum[N], len[N], rg[N];
int find(int x) {
if (x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
par[y] = x;
sum[x] += sum[y];
len[x] += len[y];
rg[x] = rg[y];
}
vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int n = (int)w.size(), q = (int)e.size();
vector<pll> at, qt;
vector<ll> ans(q);
for (int i = 0; i < n; i++) at.push_back({w[i], i});
for (int i = 0; i < q; i++) qt.push_back({e[i], i});
sort(at.begin(), at.end());
sort(qt.begin(), qt.end());
ll res = 0;
st1.build(1, 0, n - 1);
st2.build(1, 0, n - 1);
for (int i = 0; i < n; i++) {
int id = at[i].se;
if (i % 2) st2.update(1, 0, n - 1, i, a[id] - b[id]);
else st1.update(1, 0, n - 1, i, a[id] - b[id]);
par[i] = i, len[i] = 1;
rg[i] = i, sum[i] = b[id];
res += a[id];
}
priority_queue<pll> pq1, pq2;
for (int i = 0; i < n - 1; i++) {
pq1.push({-(at[i + 1].fi - at[i].fi), i});
}
for (int i = 1; i < n - 1; i++) {
pq2.push({-(at[i + 1].fi - at[i - 1].fi), i});
}
for (int i = 0; i < q; i++) {
while (!pq1.empty() and -pq1.top().fi <= qt[i].fi) {
int x = pq1.top().se, y = x + 1;
pq1.pop();
x = find(x), y = find(y);
res -= sum[x] + sum[y];
if (len[x] % 2) {
if (x % 2) res -= st2.get(1, 0, n - 1, x, rg[x]);
else res -= st1.get(1, 0, n - 1, x, rg[x]);
}
if (len[y] % 2) {
if (y % 2) res -= st2.get(1, 0, n - 1, y, rg[y]);
else res -= st1.get(1, 0, n - 1, y, rg[y]);
}
merge(x, y);
res += sum[x];
if (len[x] % 2) {
if (x % 2) res += st2.get(1, 0, n - 1, x, rg[x]);
else res += st1.get(1, 0, n - 1, x, rg[x]);
}
}
while (!pq2.empty() and -pq2.top().fi <= qt[i].fi) {
int x = pq2.top().se;
pq2.pop();
int px = find(x);
if (len[px] % 2) {
if (px % 2) res -= st2.get(1, 0, n - 1, px, rg[px]);
else res -= st1.get(1, 0, n - 1, px, rg[px]);
}
int id = at[x].se;
st1.update(1, 0, n - 1, x, a[id] - b[id]);
st2.update(1, 0, n - 1, x, a[id] - b[id]);
if (len[px] % 2) {
if (px % 2) res += st2.get(1, 0, n - 1, px, rg[px]);
else res += st1.get(1, 0, n - 1, px, rg[px]);
}
}
ans[qt[i].se] = res;
}
return ans;
}
/*
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5
9
1
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
1
5
*/
