#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
const ll LINF = 1e18;
const int b = 8;
const int max_log = 9;
int n;
vector< vector<vi> > up; // [k][u][i]: 2^i steps from u, strength [2 ^ k, 2 ^ (k + 1))
vector< vector<vll> > gain, to_win;
vi s, p, w, l;
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;
s.push_back(0); p.push_back(0); w.push_back(n); l.push_back(n);
up.assign(max_log + 1, vector<vi>(n + 1, vi(max_log + 1)));
gain.assign(max_log + 1, vector<vll>(n + 1, vll(max_log + 1)));
to_win.assign(max_log + 1, vector<vll>(n + 1, vll(max_log + 1)));
for (int k = 0, pw = 1; k <= max_log; k++, pw *= b) {
for (int u = 0; u <= n; u++) {
up[k][u][0] = (s[u] < pw ? w[u] : l[u]);
gain[k][u][0] = (s[u] < pw ? s[u] : p[u]);
to_win[k][u][0] = (s[u] < pw * b ? s[u] : LINF);
}
for (int i = 1; i <= max_log; i++) {
for (int u = 0; u <= n; u++) {
up[k][u][i] = up[k][up[k][u][i - 1]][i - 1];
gain[k][u][i] = gain[k][u][i - 1] + gain[k][up[k][u][i - 1]][i - 1];
to_win[k][u][i] = min(to_win[k][u][i - 1], to_win[k][up[k][u][i - 1]][i - 1] - gain[k][u][i - 1]);
}
}
}
}
long long simulate(int x, int z) {
ll ans = z, pw = 1;
int k = 0, u = x;
while (pw * b <= z) pw *= b, k++;
while (u != n) {
while (u != n && ans < pw * b) {
for (int i = max_log; i >= 0; i--) {
if (ans + gain[k][u][i] <= pw * b && ans < to_win[k][u][i]) {
ans += gain[k][u][i];
u = up[k][u][i];
}
}
if (ans < s[u]) ans += p[u], u = l[u];
else ans += s[u], u = w[u];
}
pw *= b;
k++;
}
return ans;
}
