#include <bits/stdc++.h>
#include "dungeons.h"
#define ll int64_t
using namespace std;
int r = 27, N;
vector<vector<ll>> P, B, 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);
MNP.resize(n + 1);
// sum - s
B.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];
for (int i = 0; i <= n; i++)
B[i][0] = l[i];
for (int i = 0; i < n; i++)
SP[i][0] = s[i];
for (int i = 0; i < n; i++)
SB[i][0] = p[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];
for (int j = 1; j < r; j++)
for (int i = 0; i <= n; i++)
B[i][j] = B[P[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];
for (int j = 1; j < r; j++)
for (int i = 0; i <= n; i++)
SB[i][j] = SB[i][j - 1] + SB[B[i][j - 1]][j - 1];
for (int i = 0; i <= n; i++)
MNP[i][0] = s[i] - s[w[i]];
for (int i = 0; i <= n; i++)
MNB[i][0] = p[i] - p[l[i]];
for (int j = 1; j < r; j++)
for (int i = 0; i <= n; i++)
MNP[i][j] = min({MNP[i][j - 1], MNP[P[i][j - 1]][j - 1], SP[P[i][j]][j] - s[P[i][j]]});
for (int j = 1; j < r; j++)
for (int i = 0; i <= n; i++)
MNB[i][j] = min({MNB[i][j - 1], MNB[P[i][j - 1]][j - 1], SB[P[i][j]][j] - p[P[i][j]]});
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;
}
