#include "dungeons.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxd1 = 8, maxd2 = 24, maxn = 4e5 + 5, base = 8;
const ll inf = 1e18 + 5ll;
vector<pair<int, int> > g[maxn];
int kam[maxd1][maxd2][maxn], pw[maxd1+1], n;
vector<int> s, p, w, l;
ll sum[maxd1][maxd2][maxn], mini[maxd1][maxd2][maxn], onlywin[maxn];
void dfs(int u, ll w)
{
onlywin[u] = w;
for (pair<int, int> i : g[u]) dfs(i.first, w+i.second);
}
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
s.push_back(0), p.push_back(0), w.push_back(n), l.push_back(n);
::n = n, ::s = s, ::p = p, ::w = w, ::l = l;
pw[0] = 1;
for (int i = 1; i <= maxd1; i++) pw[i] = pw[i-1] * base;
for (int i = 0; i < maxd1; i++)
{
for (int j = 0; j <= n; j++)
{
if (s[j] <= pw[i])
{
sum[i][0][j] = s[j], kam[i][0][j] = w[j];
mini[i][0][j] = inf;
}
else
{
sum[i][0][j] = p[j], kam[i][0][j] = l[j];
mini[i][0][j] = s[j];
}
}
for (int j = 1; j < maxd2; j++) for (int k = 0; k < maxn; k++)
{
kam[i][j][k] = kam[i][j-1][kam[i][j-1][k]];
sum[i][j][k] = sum[i][j-1][k] + sum[i][j-1][kam[i][j-1][k]];
mini[i][j][k] = min(mini[i][j-1][k], mini[i][j-1][kam[i][j-1][k]] - sum[i][j-1][k]);
}
}
for (int i = 0; i < n; i++) g[w[i]].push_back({i, s[i]});
dfs(n, 0);
}
ll simulate(int x, int z)
{
ll st = z;
for (int i = 0; i < maxd1; i++)
{
while (x != n && st < pw[i+1])
{
for (int j = maxd2-1; j >= 0; j--) if (mini[i][j][x] > st)
{
st += sum[i][j][x];
x = kam[i][j][x];
}
st += s[x];
x = w[x];
}
}
return st + onlywin[x];
}
