#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
using ll = long long;
long long dp[8][400001][26] , sum[8][400001][26]; // last er tate just answer rakhbo or something;
// minimum koto lagbe and kothai lagbe
long long ans[400001] , one , two , jog;
int ek , dui , shesh[8][400001][26] , star , here , nn , pos[8][400001][26];
vector<int> sa , wa , pa , la;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l ) {
sa = s;
wa = w;
la = l;
pa = p;
nn = n;
ll ten = 1;
for( int z = 0; z <= 7; z++ ) {
if( z > 0 ) ten = ten * ll(10);
dp[z][n][0] = 0;
pos[z][n][0] = n;
sum[z][n][0] = 0;
shesh[z][n][0] = n;
for( int y = 0; y < n; y++ ){
if( s[y] >= ten ) {
dp[z][y][0] = s[y];
pos[z][y][0] = y;
sum[z][y][0] = 0; //eta kheytal rakhio
//shesh?
}
else{
dp[z][y][0] = 1e13;
pos[z][y][0] = -1;
sum[z][y][0] = 0; //eta kheytal rakhio
}
}
for( int x = 1; x <= 25; x++ ) {
dp[z][n][x] = 0;
pos[z][n][x] = n;
sum[z][n][x] = 0;
shesh[z][n][x] = n;
for( int y = 0; y < n; y++ ) {
if( x == 1 ) {
if( s[y] >= ten ) {
one = p[y];
ek = l[y];
}
else{
one = s[y];
ek = w[y];
}
sum[z][y][x] = one;
dp[z][y][x] = dp[z][y][x - 1];
pos[z][y][x] = pos[z][y][x - 1];
shesh[z][y][x] = ek;
if( dp[z][y][x] > (dp[z][ek][x - 1] - sum[z][y][x]) ) {
dp[z][y][x] = (dp[z][ek][x - 1] - sum[z][y][x]);
pos[z][y][x] = pos[z][ek][x - 1];
}
}
else{
sum[z][y][x] = sum[z][y][x - 1] + sum[z][shesh[z][y][x - 1]][x - 1];
shesh[z][y][x] = shesh[z][shesh[z][y][x - 1]][x - 1];
dp[z][y][x] = dp[z][y][x - 1];
pos[z][y][x] = pos[z][y][x - 1];
if( dp[z][y][x] > dp[z][shesh[z][y][x - 1]][x - 1] - sum[z][y][x - 1] ) {
dp[z][y][x] = dp[z][shesh[z][y][x - 1]][x - 1] - sum[z][y][x - 1];
pos[z][y][x] = pos[z][shesh[z][y][x - 1]][x - 1];
}
}
}
}
}
ans[n] = 0;
for( int z = n - 1; z >= 0; z-- ) {
ans[z] = ans[w[z]] + s[z];
}
return;
}
long long simulate(int x, int zz) {
here = (int)x;
jog = (ll)zz;
ll ten = 1;
for( int z = 0; z <= 7; z++ ) {
if( z > 0 ) ten = ten * (ll)10;
while( jog < ten * (ll)10 && here != nn ) {
for( int y = 25; y >= 1; y-- ) {
if( dp[z][here][y] > jog ) {
jog += sum[z][here][y];
here = shesh[z][here][y];
y++;
}
}
if( dp[z][here][0] > jog ) {
jog += sum[z][here][1];
here = shesh[z][here][1];
}
if( here != nn ) {
cerr << here << " " << jog << "\n";
jog += (ll)sa[here];
here = wa[here];
}
}
}
return jog;
}
