#include "dungeons.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
using namespace std;
int N;
vector<int> s, p, w, l;
vector<int> ss;
vector<vector<vector<pair<int, pair<int, int>>>>> nxt;
vector<long long> tw;
const int LOG = 22;
const int MAXS = 1e7;
int sn;
long long pth(int x)
{
if (x == N)
return 0;
if (tw[x] >= 0)
return tw[x];
tw[x] = pth(w[x]) + (long long)s[x];
return tw[x];
}
void init(signed n, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L)
{
N = n;
s.resize(N);
tw.resize(N, -1);
p.resize(N);
w.resize(N + 1);
l.resize(N + 1);
l[N] = N;
w[N] = N;
for (int i = 0; i < n; i++)
{
s[i] = S[i];
p[i] = P[i];
w[i] = W[i];
l[i] = L[i];
}
ss.push_back(0);
int u = 1;
ss.push_back(u);
while (u < MAXS)
{
u *= 6;
ss.push_back(u);
}
sn = sz(ss);
nxt.resize(N + 1, vector<vector<pair<int, pair<int, int>>>>(sn, vector<pair<int, pair<int, int>>>(1, {0, {0, 0}})));
for (int j = 0; j < sz(ss); j++)
{
nxt[N][j][0].first = 0;
nxt[N][j][0].second.first = N;
nxt[N][j][0].second.second = 1e8;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < sz(ss); j++)
{
if (s[i] <= ss[j])
{
nxt[i][j][0].first = s[i];
nxt[i][j][0].second.first = w[i];
nxt[i][j][0].second.second = 1e8;
}
else
{
nxt[i][j][0].first = p[i];
nxt[i][j][0].second.first = l[i];
nxt[i][j][0].second.second = s[i];
}
}
}
for (int j = 1; j < LOG; j++)
{
for (int i = 0; i <= N; i++)
{
for (int k = 0; k < sz(ss); k++)
{
if (j > sz(nxt[i][k]) || nxt[i][k][j - 1].second.first == N || j > sz(nxt[nxt[i][k][j - 1].second.first][k]) || nxt[i][k][j - 1].second.second <= ss[k] || nxt[nxt[i][k][j - 1].second.first][k][j - 1].second.second - nxt[i][k][j - 1].first <= ss[k])
continue;
nxt[i][k].push_back({nxt[i][k][j - 1].first + nxt[nxt[i][k][j - 1].second.first][k][j - 1].first, {nxt[nxt[i][k][j - 1].second.first][k][j - 1].second.first, min(nxt[i][k][j - 1].second.second, nxt[nxt[i][k][j - 1].second.first][k][j - 1].second.second - nxt[i][k][j - 1].first)}});
}
}
}
return;
}
int cs, u;
long long simulate(signed x, signed z)
{
cs = z;
u = x;
for (int i = 0; i < sz(ss); i++)
{
while (ss[i + 1] > cs)
{
for (int j = LOG - 1; j >= 0; j--)
{
if (j >= sz(nxt[u][i]) || nxt[u][i][j].second.first == N || nxt[u][i][j].second.second <= cs)
continue;
cs += nxt[u][i][j].first;
u = nxt[u][i][j].second.first;
}
if (nxt[u][i][0].second.first == N)
{
if (s[u] > cs)
cs += p[u];
else
cs += s[u];
return cs;
}
else
{
if (s[u] > cs)
cs += p[u],
u = l[u];
else
cs += s[u],
u = w[u];
}
if (u == N)
return cs;
}
}
return (long long)cs + pth(u);
}
