#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 400000;
const int lg2 = 20;
const int lg10 = 8;
const long long inf = 1e9;
int to[lg10][lg2][mxN];
int lim[lg10][lg2][mxN];
long long add[lg10][lg2][mxN];
int pw[lg10];
int n;
vector<int> s, p, w, l;
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n = _n, s = _s, p = _p, w = _w, l = _l;
pw[0] = 1;
for (int i = 1; i < lg10; i++) pw[i] = pw[i - 1] * 10;
for (int i = 0; i < n; i++) {
for (int j = 0; j < lg10; j++) {
if (pw[j] >= s[i]) {
to[j][0][i] = w[i];
add[j][0][i] = s[i];
lim[j][0][i] = inf;
} else {
to[j][0][i] = l[i];
add[j][0][i] = p[i];
lim[j][0][i] = s[i];
}
}
}
for (int i = 0; i < lg10; i++) {
for (int j = 1; j < lg2; j++) {
for (int k = 0; k < n; k++) {
if (to[i][j - 1][k] == n) {
to[i][j][k] = n;
continue;
}
to[i][j][k] = to[i][j - 1][to[i][j - 1][k]];
add[i][j][k] = add[i][j - 1][k] + add[i][j - 1][to[i][j - 1][k]];
if (lim[i][j - 1][to[i][j - 1][k]] == inf) lim[i][j][k] = lim[i][j - 1][k];
else lim[i][j][k] = min(1LL * lim[i][j - 1][k], max(0LL, 1LL * lim[i][j - 1][to[i][j - 1][k]] - add[i][j - 1][k]));
}
}
}
return;
}
long long simulate(int x, int _z) {
long long z = _z;
while (x != n) {
int c = 0;
while (c + 1 < lg10 && pw[c + 1] <= z) c++;
for (int j = lg2 - 1; j >= 0; j--) {
if (lim[c][j][x] != inf && z >= lim[c][j][x]) continue;
if (to[c][j][x] == n) continue;
z += add[c][j][x];
x = to[c][j][x];
}
if (x == n) break;
if (z >= s[x]) {
z += s[x];
x = w[x];
} else {
z += p[x];
x = l[x];
}
}
return z;
}
