// Be Name Khoda //
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
const int maxn5 = 4e5 + 5;
const int lgr = 27;
const int lgl = 15;
int n, par[lgr - lgl + 1][lgr][maxn5];
int s[maxn5], p[maxn5], w[maxn5], l[maxn5];
ll val[lgr - lgl + 1][lgr][maxn5];
int get_lev(ll x){
return 63 - __builtin_clzll(x);
}
void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll) {
n = nn;
for(int i = 0; i < n; i++){
s[i] = ss[i];
p[i] = pp[i];
w[i] = ww[i];
l[i] = ll[i];
}
memset(par, -1, sizeof par);
for(int x = 0; x < lgr - lgl; x++){
for(int i = 0; i < n; i++){
if(get_lev(s[i]) == x + lgl)
continue;
int re = ((1 << (x + lgl)) >= s[i]);
par[x][0][i] = re ? w[i] : l[i];
val[x][0][i] = re ? s[i] : p[i];
}
for(int i = 0; i < n; i++)
for(int k = 1; k < lgr && par[x][k - 1][i] != -1; k++){
par[x][k][i] = par[x][k - 1][par[x][k - 1][i]];
val[x][k][i] = val[x][k - 1][i] + val[x][k - 1][par[x][k - 1][i]];
}
}
return;
}
long long simulate(int x, int zz) {
ll ret = zz;
while(ret < (1 << lgl) && x < n){
bool re = ret >= s[x];
ret += (re ? s[x] : p[x]);
x = (re ? w[x] : l[x]);
}
while(x < n){
int lev = get_lev(ret);
if(lev >= lgr)
return 0;
ll lev2 = (1ll << (lev + 1));
//debug(lev);
//debug(x);
//debug(ret);
lev -= lgl;
for(int i = lgr - 1; i >= 0; i--)
if(par[lev][i][x] != -1 && ret + val[lev][i][x] < lev2){
ret += val[lev][i][x];
x = par[lev][i][x];
}
if(x == n)
return ret;
//debug(x);
//debug(ret);
bool re = ret >= s[x];
ret += (re ? s[x] : p[x]);
x = (re ? w[x] : l[x]);
}
return ret;
}
