#include "dungeons.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 400005;
// baza 8
int N, putere[8];
pair<pair<long long, long long>,int>lca[nmax][24][8];
vector<int>S, W;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
putere[0] = 1;
for(int i=1;i<=7;i++) putere[i] = putere[i-1] * 8;
for(auto &it : w) ++it;
for(auto &it : l) ++it;
S = s; W = w;
N = n;
for(int j=0;j<=7;j++){
for(int i=1;i<=n;i++){
if(s[i - 1] < putere[j]){
lca[i][0][j].sc = w[i - 1];
lca[i][0][j].fr.fr = s[i - 1];
lca[i][0][j].fr.sc = -1e18;
}
else{
lca[i][0][j].sc = l[i - 1];
lca[i][0][j].fr.fr = p[i - 1];
lca[i][0][j].fr.sc = -s[i - 1];
}
}
}
for(int k=1;k<=23;k++){
for(int j=0;j<=7;j++){
for(int i=1;i<=n;i++){
int slavic = lca[i][k-1][j].sc;
lca[i][k][j].fr.fr = lca[i][k-1][j].fr.fr;
lca[i][k][j].fr.sc = lca[i][k-1][j].fr.sc;
for(int lol=1;lol<=1;lol++){
lca[i][k][j].fr.sc = max(lca[i][k][j].fr.sc, lca[i][k][j].fr.fr + lca[slavic][k-1][j].fr.sc);
lca[i][k][j].fr.fr += lca[slavic][k-1][j].fr.fr;
slavic = lca[slavic][k-1][j].sc;
}
lca[i][k][j].sc = slavic;
}
}
}
}
long long simulate(int x, int z) {
int pos_curr = x + 1;
long long putere_curr = z;
int i = 0;
int t = 0;
while(pos_curr != N + 1){
if(t == 7){
i++;
t = 0;
}
if(i == 8) break;
for(int j=7;j>=0;j--){
for(int pizdet=1;pizdet<=1;pizdet++){
if(lca[pos_curr][j][i].sc && lca[pos_curr][j][i].fr.sc + putere_curr < 0LL){
putere_curr += lca[pos_curr][j][i].fr.fr;
pos_curr = lca[pos_curr][j][i].sc;
}
else break;
}
}
if(pos_curr == N + 1) break;
else{
++t;
putere_curr += (long long)S[pos_curr - 1];
pos_curr = W[pos_curr - 1];
}
}
while(pos_curr != N + 1){
putere_curr += (long long)S[pos_curr - 1];
pos_curr = W[pos_curr - 1];
}
return putere_curr;
}
