#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MAXN = 4e5+5, C = 4, lC = 13;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int N, nxt[lC][24][MAXN], sum[lC][24][MAXN], mind[lC][24][MAXN];
// mind = min(s - sum)
vi S, W;
void init(int n, vi s, vi p, vi w, vi l) {
N = n;
S = s;
W = w;
for(int R = 0, pot = 1; R < lC and pot <= 1e7; pot *= C, R++) {
// pot, pot*C-1
nxt[R][0][n] = n;
mind[R][0][n] = 1e9;
for(int i = 0; i < n; i++) {
if(s[i] <= pot) nxt[R][0][i] = w[i], sum[R][0][i] = s[i], mind[R][0][i] = 1e9;
else nxt[R][0][i] = l[i], sum[R][0][i] = p[i], mind[R][0][i] = s[i];
}
for(int b = 1; b < 24; b++) {
for(int i = 0; i <= n; i++) {
nxt[R][b][i] = nxt[R][b-1][nxt[R][b-1][i]];
sum[R][b][i] = sum[R][b-1][i] + sum[R][b-1][nxt[R][b-1][i]];
mind[R][b][i] = min(mind[R][b-1][i], mind[R][b-1][nxt[R][b-1][i]] - sum[R][b-1][i]);
}
}
}
}
ll simulate(int x, int aux) {
int R = 0;
ll z = aux, pot = 1;
while(x != N) {
while(R < lC - 1 and pot*C <= z) R++, pot *= C;
for(int b = 23; b >= 0; b--)
if(mind[R][b][x] > z) z += sum[R][b][x], x = nxt[R][b][x];
if(x == N) return z;
z += S[x];
x = W[x];
}
return z;
}
