#include <bits/stdc++.h>
#include "dungeons.h"
#define ll int64_t
using namespace std;
int r = 25, N;
vector<vector<int>> P, B;
vector<vector<ll>> SP, SB, MNP, MNB;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
N = n;
s.push_back(0);
p.push_back(0);
l.push_back(n);
w.push_back(n);
P.resize(n + 1);
SP.resize(n + 1);
MNP.resize(n + 1);
// sum - s
B.resize(n + 1);
SB.resize(n + 1);
MNB.resize(n + 1);
// sum - p
for (auto &i : P)
i.resize(r);
for (auto &i : B)
i.resize(r);
for (auto &i : SP)
i.resize(r);
for (auto &i : SB)
i.resize(r);
for (auto &i : MNP)
i.resize(r);
for (auto &i : MNB)
i.resize(r);
for (int i = 0; i <= n; i++)
P[i][0] = w[i], B[i][0] = l[i], SP[i][0] = s[i], SB[i][0] = p[i], MNP[i][0] = MNB[i][0] = -s[i];
for (int j = 1; j < r; j++)
for (int i = 0; i <= n; i++)
P[i][j] = P[P[i][j - 1]][j - 1], B[i][j] = B[B[i][j - 1]][j - 1];
for (int j = 1; j < r; j++)
for (int i = 0; i <= n; i++)
SP[i][j] = SP[i][j - 1] + SP[P[i][j - 1]][j - 1], SB[i][j] = SB[i][j - 1] + SB[B[i][j - 1]][j - 1];
for (int j = 1; j < r; j++)
for (int i = 0; i <= n; i++)
MNP[i][j] = min(MNP[i][j - 1], SP[i][j - 1] + MNP[P[i][j - 1]][j - 1]);
for (int j = 1; j < r; j++)
for (int i = 0; i <= n; i++)
MNB[i][j] = max(MNB[i][j - 1], SB[i][j - 1] + MNB[B[i][j - 1]][j - 1]);
return;
}
long long simulate(int x, int Z)
{
ll z = Z;
while (x < N)
{
for (int i = r - 1; i >= 0; i--)
if (MNP[x][i] + z >= 0 && P[x][i] < N)
z += SP[x][i], x = P[x][i];
for (int i = r - 1; i >= 0; i--)
if (MNB[x][i] + z < 0 && B[x][i] < N)
z += SB[x][i], x = B[x][i];
if (x == N)
break;
if (z >= SP[x][0])
z += SP[x][0], x = P[x][0];
else
z += SB[x][0], x = B[x][0];
}
return z;
}
