#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef local
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template <typename ...T> void qqbx(const char *s, T ... a) {
int cnt = sizeof...(T);
((std::cerr << "\e[1;32m(" << s << ") = ("), ... ,(std::cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
std::cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L) std::cerr << (f++ ? ", " : "") << *L;
std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)
using ll = long long;
const ll INF = 1e18;
const int inf = 1e7, K = 5, PHASE = 10;
const int LG = 30, maxn = 400025;
struct node {
ll p;
int lim;
int to;
friend node operator+(const node &lhs, const node &rhs) {
node res;
res.p = min(INF, lhs.p + rhs.p);
res.lim = max<ll>(0, min<ll>(lhs.lim, rhs.lim - lhs.p));
res.to = rhs.to;
return res;
}
node () : p(0), lim(inf), to(-1) {}
node (ll _p, int _lim, int _to) : p(_p), lim(_lim), to(_to) {}
};
node st[3][maxn];
node nxt[LG][PHASE][maxn]; // 300 step, 90000 step
int n;
vector<int> s, p, w, l;
long long winwin[maxn];
void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
n = _n, s = _s, p = _p, w = _w, l = _l;
st[0][n] = {0, 0, n};
for (int lev = 0; lev < LG; lev++) {
for (int i = 0; i < n; i++) {
if (s[i] <= (1LL<<lev)) {
nxt[lev][0][i] = { s[i], inf, w[i] };
} else {
nxt[lev][0][i] = { p[i], s[i], l[i] };
}
}
nxt[lev][0][n] = { 0, 0, n };
for (int phase = 1; phase < PHASE; phase++) {
for (int i = 0; i < n; i++) st[0][i] = nxt[lev][phase-1][i];
for (int i = 0; i <= n; i++) nxt[lev][phase][i].to = i;
for (int L = 0; L < 3; L++) {
if (K >> L & 1) {
for (int i = 0; i <= n; i++) {
auto &nd = nxt[lev][phase][i];
nd = nd + st[L][nd.to];
}
}
if (L+1 < 3) for (int i = 0; i <= n; i++) st[L+1][i] = st[L][i] + st[L][st[L][i].to];
}
}
}
winwin[n] = 0;
for (int i = n-1; i >= 0; i--)
winwin[i] = winwin[w[i]] + s[i];
return;
}
long long simulate(int x, int _z) {
long long z = _z;
while (x != n && z < inf) {
long long org_z = z;
int lev = __lg(z);
for (int phase = PHASE-1; phase >= 0; phase--) {
for (int it = 0; it < K; it++) {
if (z < nxt[lev][phase][x].lim) {
z += nxt[lev][phase][x].p;
x = nxt[lev][phase][x].to;
}
}
}
if (x == n)
return z;
assert (z >= s[x]);
z += s[x];
x = w[x];
if (x == n)
return z;
// assert (__lg(z) > __lg(org_z));
}
return z + winwin[x];
}
