#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
int X,Y,n,W[400000],L[400000],ps[9][400000][24];
ll s[400000],p[400000],sm[9][400000][24],th[9][400000][24];
vector<ll> pw;
void init(int N, std::vector<int> arr, std::vector<int> P, std::vector<int> w, std::vector<int> l) {
X=9;n=N;
Y=24;
REP(i,0,n)W[i]=w[i];
REP(i,0,n)L[i]=l[i];
REP(i,0,n)s[i]=(ll)arr[i];
REP(i,0,n)p[i]=(ll)P[i];
pw.resize(X+1,1);
REP(i,1,X+1)pw[i]=pw[i-1]*8LL;
REP(i,0,X){
REP(j,0,n){
if(s[j]<pw[i]){
ps[i][j][0]=w[j];
sm[i][j][0]=s[j];
th[i][j][0]=INF;
}
else{
ps[i][j][0]=l[j];
sm[i][j][0]=p[j];
th[i][j][0]=s[j];
}
if(i==X-1)th[i][j][0]=INF;
}
REP(k,1,Y)REP(j,0,n){
if(ps[i][j][k-1]==n){
ps[i][j][k]=n;
continue;
}
ps[i][j][k]=ps[i][ps[i][j][k-1]][k-1];
sm[i][j][k]=sm[i][j][k-1]+sm[i][ps[i][j][k-1]][k-1];
th[i][j][k]=min(th[i][j][k-1],th[i][ps[i][j][k-1]][k-1]-sm[i][j][k-1]);
}
}
return;
}
long long simulate(int x, int z) {
ll y=(ll)z;
while(x!=n){
int t=upper_bound(all(pw),y)-pw.begin();
t--;
t=min(t,8);
for(int k=Y-1;k>=0;k--)if(ps[t][x][k]!=n&&y<th[t][x][k]){
y+=sm[t][x][k];
x=ps[t][x][k];
}
if(s[x]<=y){
y+=s[x];
x=W[x];
}
else{
y+=p[x];
x=L[x];
}
}
return y;
}
