#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 5e4 + 1;
vector<int> s, p, w, l;
int n;
int st;
// st34 initialize
int liftpar[6][mxN][25];
ll int liftsum[6][mxN][25];
vector<int> diffs = {0};
void ComputeLift() {
for (int i = 0; i < int(diffs.size()); i++) {
for (int u = 0; u < n; u++) {
if (s[u] <= diffs[i]) {
liftpar[i][u][0] = w[u];
liftsum[i][u][0] = s[u];
} else {
liftpar[i][u][0] = l[u];
liftsum[i][u][0] = p[u];
}
}
for (int dep = 1; dep < 25; dep++) {
for (int u = 0; u < n; u++) {
if (liftpar[i][u][dep - 1] == n) {
liftpar[i][u][dep] = n;
liftsum[i][u][dep] = liftsum[i][u][dep - 1];
} else {
liftpar[i][u][dep] = liftpar[i][liftpar[i][u][dep - 1]][dep - 1];
liftsum[i][u][dep] = liftsum[i][u][dep - 1] + liftsum[i][liftpar[i][u][dep - 1]][dep - 1];
}
}
}
}
}
void st34init() {
for (int i = 0; i < n; i++) {
bool appear = false;
for (int &x : diffs) {
appear |= (x == s[i]);
}
if (!appear) diffs.pb(s[i]);
}
sort(diffs.begin(), diffs.end());
ComputeLift();
}
void init(int on, vector<int> os, vector<int> op, vector<int> ow, vector<int> ol) {
n = on;
s = os; p = op; w = ow; l = ol;
bool isst2 = true;
for (int i = 0; i < n; i++) {
isst2 &= (s[i] == p[i]);
}
if (isst2) {
st = 2;
return;
} else if (n > 50000) {
st = 6;
return;
}
set<int> dists;
for (int i = 0; i < n; i++) {
dists.insert(s[i]);
if (dists.size() > 5) break;
}
if (dists.size() <= 5) {
st = 4;
st34init();
return;
}
// 1 and 5 is ???
st = 1;
return;
}
ll int st1(int x, ll int z) {
while (x != n) {
if (z >= s[x]) {
z += s[x];
x = w[x];
} else {
z += p[x];
x = l[x];
}
}
return z;
}
ll int st2(int x, ll int z) {
return 0;
}
ll int st34(int x, ll int z) {
for (int i = 0; i < int(diffs.size()); i++) {
ll int tar = (i == int(diffs.size()) - 1 ? 1e18 : diffs[i + 1]);
if (z >= tar) continue;
for (int dep = 24; dep >= 0; dep--) {
if (z + liftsum[i][x][dep] < tar) {
z += liftsum[i][x][dep];
x = liftpar[i][x][dep];
if (x == n) return z;
}
}
z += liftsum[i][x][0];
x = liftpar[i][x][0];
if (x == n) return z;
}
return -1;
}
long long simulate(int x, int z) {
if (st == 1) return st1(x, z);
if (st == 2) return st2(x, z);
if (st == 3 || st == 4) return st34(x, z);
return 0;
}
