#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int Base = 8, LN = 25, LS = 9, N = 4e5 + 5;
using ll = long long;
constexpr ll inf = 1e18;
int n;
int go[N][LS][LN];
ll lim[N][LS][LN], gain[N][LS][LN], pw[LS];
vector<int> s, p, win, lose;
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, win = W, lose = L;
for (int i = pw[0] = 1; i < LS; i++) {
pw[i] = pw[i - 1] * Base;
}
for (int C = 0; C < LS; C++) {
for (int i = 0; i < n; i++) {
if (pw[C] >= s[i]) {
if (win[i] == n) {
go[i][C][0] = -1;
} else {
go[i][C][0] = win[i];
gain[i][C][0] = s[i];
lim[i][C][0] = inf;
}
} else {
if (lose[i] == n) {
go[i][C][0] = n;
} else {
go[i][C][0] = lose[i];
gain[i][C][0] = p[i];
lim[i][C][0] = s[i];
}
}
}
}
for (int C = 0; C < LS; C++) {
for (int j = 1; j < LN; j++) {
for (int i = 0; i < n; i++) {
if (go[i][C][j - 1] == -1 || go[go[i][C][j - 1]][C][j - 1] == -1) {
go[i][C][j] = -1;
continue;
}
go[i][C][j] = go[go[i][C][j - 1]][C][j - 1];
gain[i][C][j] = gain[i][C][j - 1] + gain[go[i][C][j - 1]][C][j - 1];
lim[i][C][j] = min(lim[i][C][j - 1], lim[go[i][C][j - 1]][C][j - 1] - gain[i][C][j - 1]);
}
}
}
}
long long simulate(int x, int z) {
long long str = z, c = 0;
while (x != n) {
while (c + 1 < LS && pw[c + 1] <= str) c++;
for (int i = LN - 1; i >= 0; i--) {
if (go[x][c][i] == -1) continue;
if (str < lim[x][c][i]) {
str += gain[x][c][i];
x = go[x][c][i];
}
}
if (str >= s[x]) str += s[x], x = win[x];
else str += p[x], x = lose[x];
}
return str;
}
