#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int ex = 3;
int jl = 30;
int n;
vector<int> s, p, w, l;
ll g[50005][25][30][3];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
::n = n;
::s = s;
::s.push_back(0);
::p = p;
::p.push_back(0);
::w = w;
::w.push_back(n);
::l = l;
::l.push_back(n);
for (int k=0; k<25; k++){
for (int i=0; i<=n; i++){
if (::s[i] <= pow(ex, k)){
g[i][k][0][0] = ::w[i];
g[i][k][0][1] = ::s[i];
g[i][k][0][2] = (ll)pow(10, 9);
}
else {
g[i][k][0][0] = ::l[i];
g[i][k][0][1] = ::p[i];
g[i][k][0][1] = ::s[i];
}
}
for (int j=1; j<jl; j++){
for (int i=0; i<n+1; i++){
g[i][k][j][0] = g[g[i][k][j-1][0]][k][j-1][0];
g[i][k][j][1] = g[i][k][j-1][1]+g[g[i][k][j-1][0]][k][j-1][1];
g[i][k][j][2] = min(g[i][k][j-1][2], g[g[i][k][j-1][0]][k][j-1][2]-g[i][k][j-1][1]);
}
}
}
return;
}
ll simulate(int x, int z2){
ll z = z2;
while (x != n){
//cout << x << " " << z << endl;
int k = floor(log(z)/log(ex));
for (int j=jl-1; j>=0; j--){
if ((z + g[x][k][j][1]) < pow(ex, k+1) && z < g[x][k][j][2]){
z += g[x][k][j][1];
x = g[x][k][j][0];
}
}
if (z >= s[x]){
z += s[x];
x = w[x];
}
else {
z += p[x];
x = l[x];
}
}
return z;
}
