#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
using lli = long long;
const int MAXN = 4e5 + 10;
const int MAXK = 20;
int pjump[MAXN][MAXK];
lli psum[MAXN][MAXK];
lli pdp[MAXN][MAXK];
int sjump[MAXN][MAXK];
lli ssum[MAXN][MAXK];
lli sdp[MAXN][MAXK];
int N;
void init(int n, vector<int> ss, vector<int> ps, vector<int> ws, vector<int> ls) {
N = n;
ss.push_back(0);
ps.push_back(0);
ws.push_back(n);
ls.push_back(n);
++n;
for (int i = 0; i < n; ++i) {
pjump[i][0] = ls[i];
psum[i][0] = ps[i];
pdp[i][0] = min(ss[i], ss[ls[i]] - ps[i]);
}
for (int k = 1; k < MAXK; ++k)
for (int u = 0; u < n; ++u) {
pjump[u][k] = pjump[pjump[u][k-1]][k-1];
psum[u][k] = psum[u][k-1] + psum[pjump[u][k-1]][k-1];
pdp[u][k] = min(pdp[u][k-1], pdp[pjump[u][k-1]][k-1] - psum[u][k-1]);
}
for (int i = 0; i < n; ++i) {
sjump[i][0] = ws[i];
ssum[i][0] = ss[i];
sdp[i][0] = max(ss[i], ss[ws[i]] - ss[i]);
}
for (int k = 1; k < MAXK; ++k)
for (int u = 0; u < n; ++u) {
sjump[u][k] = sjump[sjump[u][k-1]][k-1];
ssum[u][k] = ssum[u][k-1] + ssum[sjump[u][k-1]][k-1];
sdp[u][k] = max(sdp[u][k-1], sdp[sjump[u][k-1]][k-1] - ssum[u][k-1]);
}
}
lli simulate(int u, int _z) {
// cerr << "start\n";
lli z = _z;
bool win = false;
while (u != N) {
// cerr << u << " win = " << win << "\n";
// cerr << "z = " << z << "\n";
if (!win) {
if (ssum[u][0] <= z) {
win = true;
continue;
}
for (int k = MAXK - 1; k >= 0; --k)
if (pdp[u][k] > z) {
z += psum[u][k];
u = pjump[u][k];
}
z += psum[u][0];
u = pjump[u][0];
win = true;
}
else {
if (ssum[u][0] > z) {
win = false;
continue;
}
for (int k = MAXK - 1; k >= 0; --k)
if (sdp[u][k] <= z) {
z += ssum[u][k];
u = sjump[u][k];
}
z += ssum[u][0];
u = sjump[u][0];
win = false;
}
}
return z;
}
