#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
#define maxn 400001
#define lgn 9
#define base 6
#define INF 1023456789123456789
int n,to[lgn+1][lgn][maxn];
ll gain[lgn+1][lgn][maxn],mn[lgn+1][lgn][maxn],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[k][0][i]=(s[i]<pwr[k])?w[i]:l[i];
gain[k][0][i]=(s[i]<pwr[k])?s[i]:p[i];
mn[k][0][i]=(s[i]<pwr[k])?INF:s[i];
}
to[k][0][n]=n;
gain[k][0][n]=0;
mn[k][0][n]=INF;
for(int j=1;j<lgn;++j){
for(int i=0;i<=n;++i){
int cur=i;
mn[k][j][i]=INF;
for(int b=0;b<base;++b){
to[k][j][i]=to[k][j-1][cur];
mn[k][j][i]=min(mn[k][j][i],mn[k][j-1][cur]-gain[k][j][i]);
gain[k][j][i]+=gain[k][j-1][cur];
cur=to[k][j-1][cur];
if(cur==n)break;
}
}
}
}
}
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[lgn][lgn-1][cur];
cur=to[lgn][lgn-1][pos];
if(cur==n)break;
}
return str;
}
for(int j=lgn-1;j>=0;--j){
for(int b=0;b<base-1;++b){
if(str<mn[k][j][pos]){
str+=gain[k][j][pos];
pos=to[k][j][pos];
}
else break;
}
}
if(pos!=n){
str+=s[pos];
pos=w[pos];
}
}
return str;
}
