#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define para pair<ll, ll>
const ll LOG = 16;
const ll LOG2 = 24;
const ll MAXN = 50007;
const ll INF = 1e9+7;
struct Str{
ll v;
ll sum;
ll mn;
};
Str jump[MAXN][LOG][LOG2];
ll n;
vector<ll> s;
vector<ll> p;
vector<ll> w;
vector<ll> l;
void gen(int x){
ll h = (1<<x);
for(int i = 0; i < n; ++i){
if(h < s[i]){
jump[i][0][x] = {l[i], p[i], s[i]};
}
else{
// if(i == n-1){
// jump[i][0][x] = {w[i], s[i], INF};
// }
jump[i][0][x] = {w[i], s[i], INF};
}
}
jump[n][0][x] = {n, 0, INF};
for(int i = 1; i < LOG; ++i){
for(int j = 0; j < n; ++j){
Str & cur = jump[j][i][x];
cur.v = jump[jump[j][i-1][x].v][i-1][x].v;
cur.sum = jump[j][i-1][x].sum + jump[jump[j][i-1][x].v][i-1][x].sum;
cur.mn = min(jump[j][i-1][x].mn, jump[jump[j][i-1][x].v][i-1][x].mn - jump[j][i-1][x].sum);
// if(x == 1 && i == 1 && j == 0){
// cerr << jump[j][i-1][x].v << " " << jump[j][i-1][x].sum << " " << jump[j][i-1][x].mn << "\n";
// cerr << jump[jump[j][i-1][x].v][i-1][x].mn << "\n";
// cerr << cur.v << " " << cur.sum << " " << cur.mn << "\n";
// }
}
}
return;
}
void init(int nT, vector<int> sT, vector<int> pT, vector<int> wT, vector<int> lT){
n = nT;
for(auto i : sT) s.push_back(i);
s.shrink_to_fit();
for(auto i : pT) p.push_back(i);
p.shrink_to_fit();
for(auto i : wT) w.push_back(i);
w.shrink_to_fit();
for(auto i : lT) l.push_back(i);
l.shrink_to_fit();
for(int i = 0; i < LOG2; ++i){
gen(i);
}
return;
}
long long simulate(int x, int zT) {
ll z = zT;
ll cnt = 0;
while(x != n){
ll pot2 = 1;
ll wyk = 0;
while(pot2 * 2 <= z) pot2*=2, ++wyk;
for(int j = LOG-1; j >= 0; --j){
// cerr << j << ":\n";
// cerr << " " << x << " " << z << " " << pot2 << ": " << jump[x][j][wyk].v << " " << jump[x][j][wyk].mn << " " << jump[x][j][wyk].sum << '\n';
if(jump[x][j][wyk].mn > z){
z += jump[x][j][wyk].sum;
x = jump[x][j][wyk].v;
}
}
if(x == n) break;
z += s[x];
x = w[x];
// if(++cnt == 5){
// cerr << "\n";
// return 0;
// }
}
return z;
}
