#include "dungeons.h"
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
using vi = vector<int>;
using ll = long long;
const int B = 4;
const int C = 3;
const int MPB = 14; /// log(MV) / log(B)
const int MK = 12; /// log(N) / log(C)
const int MN = 400000;
const int MV = 5e7;
const ll INF = 1e18;
struct salt {
int u; // in ce nod am ajuns
ll delta, smax;
salt operator+(const salt &rhs) {
salt re; /// prima data fac eu, dupa rhs
if(smax == INF && rhs.smax == INF) re.smax = INF;
else
re.smax = min(smax, rhs.smax - delta);
re.delta = rhs.delta + delta;
re.u = rhs.u;
return re;
}
};
salt DP[MN][MPB][MK];
int n;
vi s, delta_l, w, l;
void init(int n0, vi s0, vi delta_l0, vi w0, vi l0) {
n = n0;
s = s0; delta_l = delta_l0; w = w0; l = l0;
ll pow = 1;
for(int p = 0; p < MPB; ++p) {
///pow... pow * B - 1
for(int i = 0; i < n; ++i) {
if(s[i] <= pow) {
DP[i][p][0] = salt{w[i], s[i], INF};
} else {
DP[i][p][0] = salt{l[i], delta_l[i], s[i] - 1};
}
}
for(int k = 1; k < MK; ++k) {
/// C ^ k e saltul
for(int i = 0; i < n; ++i) {
salt eu = DP[i][p][k - 1];
for(int j = 1; j < C; ++j) {
if(eu.u == n) break;
salt nou = DP[eu.u][p][k - 1];
eu = eu + nou;
}
DP[i][p][k] = eu;
}
}
pow *= B;
}
return;
}
int nr_op = 0;
int nr_run = 0;
ll simulate(int x, int z0) {
++nr_run;
ll p = 0, pow = 1;
ll z = z0;
while(x < n) {
while(p + 1 < MPB && pow * B <= min(z, (ll)MV)) {
++p; pow *= B;
}
for(int k = MK - 1; k >= 0; --k) {
while(x < n) { /// max C ori rulata
++nr_op;
salt eu = DP[x][p][k];
if(eu.smax < z) break;
x = eu.u;
z += eu.delta;
}
if(x == n) break;
}
if(x == n) break;
if(z >= s[x]) {
z += s[x];
x = w[x];
} else {
z += delta_l[x];
x = l[x];
}
}
return z;
}
