#include "dungeons.h"
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;
const int MAXN = 4e5 + 123;
const int LOGVL = 26;
const ll INF = 1e9;
int n;
int edg[MAXN][2];
int p[MAXN][2];
pair<int, ll> cpredg0[LOGVL][MAXN];
pair<int, ll> cpredg1[LOGVL][MAXN];
int rpw2(int x){
int lb = 0, ub = LOGVL;
while(ub - lb > 1){
int mb = (lb + ub) / 2;
if((1 << mb) <= x){
lb = mb;
} else {
ub = mb;
}
}
return lb;
}
void get_next(ll& i, ll& vl){
if(i >= n)
return;
if(vl >= p[i][0]){
vl += p[i][0];
i = edg[i][0];
} else {
vl += p[i][1];
i = edg[i][1];
}
}
void init(int n0, vector<int> sv, vector<int> pv, vector<int> wv, vector<int> lv) {
n = n0;
for(int i = 0; i < n; ++i){
edg[i][0] = wv[i];
edg[i][1] = lv[i];
p[i][0] = sv[i];
p[i][1] = pv[i];
}
for(int lyr = 0; lyr < LOGVL; ++lyr){
for(int i = 0; i < n; ++i){
ll x = i, z = (1 << lyr);
cpredg1[lyr][i] = cpredg0[lyr][i] = {x, 0};
while(x < n && z >= p[x][0]){
cpredg0[lyr][i] = {x, z - (1 << lyr)};
get_next(x, z);
}
x = i, z = (1 << lyr);
while(x < n && z < p[x][0]){
cpredg1[lyr][i] = {x, z - (1 << lyr)};
get_next(x, z);
}
}
}
//for(int lyr = 1; lyr < LOGVL; ++lyr){
//for(int i = 0; i < n; ++i){
//ll x = i, z = (1 << lyr);
//while(x ==z >= p[x][0]){
//cpredg0[lyr][i] = {x, z - (1 << lyr)};
//if(x >= n)
//break;
//}
//}
//}
return;
}
ll simulate(int x, int z){
ll ans = z;
ll i = x;
while(i < n){
ll lgans = rpw2(ans);
ans += cpredg0[lgans][i].second;
i = cpredg0[lgans][i].first;
if(ans < 1e7){
ans += cpredg1[lgans + 1][i].second;
i = cpredg1[lgans + 1][i].first;
}
get_next(i, ans);
}
return ans;
}
