#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 400001
#define lgn 8
#define base 8
#define INF 1023456789123456789
int n,to[maxn][lgn][lgn+1];
ll gain[maxn][lgn][lgn+1],mn[maxn][lgn][lgn+1],pwr[lgn+2];
vector<int> s,w;
void init(int _n,vector<int> _s,vector<int> p,vector<int> _w,vector<int> l){
pwr[0]=1;
for(int i=1;i<=lgn+1;++i)pwr[i]=pwr[i-1]*base;
n=_n;s=_s;w=_w;
for(int k=0;k<=lgn;++k){//win if <base^k, lose if >=base^k
for(int i=0;i<n;++i){
to[i][0][k]=(s[i]<pwr[k])?w[i]:l[i];
gain[i][0][k]=(s[i]<pwr[k])?s[i]:p[i];
mn[i][0][k]=(s[i]<pwr[k])?INF:s[i];
}
to[n][0][k]=n;
gain[n][0][k]=0;
mn[n][0][k]=INF;
for(int j=1;j<lgn;++j){
for(int i=0;i<=n;++i){
int cur=i;
mn[i][j][k]=INF;
for(int b=0;b<base;++b){
to[i][j][k]=to[cur][j-1][k];
mn[i][j][k]=min(mn[i][j][k],mn[cur][j-1][k]-gain[i][j][k]);
gain[i][j][k]+=gain[cur][j-1][k];
cur=to[cur][j-1][k];
}
}
}
}
}
ll simulate(int x,int z){
ll str=z;
int pos=x;
while(pos!=n){
int k=0;
while(pwr[k+1]<=str)++k;
if(k>lgn){
int cur=pos;
for(int b=0;b<base-1;++b){
str+=gain[cur][lgn-1][lgn];
cur=to[pos][lgn-1][lgn];
}
return str;
}
for(int j=lgn-1;j>=0;--j){
for(int b=0;b<base-1;++b){
if(str<mn[pos][j][k]){
str+=gain[pos][j][k];
pos=to[pos][j][k];
}
}
}
if(pos!=n){
str+=s[pos];
pos=w[pos];
}
}
return str;
}
