#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400005;
const int K=25;
const ll inf=1e18;
const int S=1e7;
int n;
int s[N],p[N],w[N],l[N];
struct edge{
int to;
ll add,lim;
edge(){}
edge(int to,ll add,ll lim):to(to),add(add),lim(lim){}
}dp[K][N][2];
void init(int _n,vector<int> _s,vector<int> _p,vector<int> _w,vector<int> _l){
n=_n;
for(int i=0;i<n;i++)s[i]=_s[i],p[i]=_p[i],w[i]=_w[i],l[i]=_l[i];
s[n]=p[n]=0;
w[n]=l[n]=n;
for(int i=0;i<K;i++){
for(int u=0;u<n;u++){
if(s[u]<=(1<<i)){
dp[i][u][0]=edge(w[u],s[u],inf);
}else{
dp[i][u][0]=edge(l[u],p[u],s[u]);
}
}
dp[i][n][0]=dp[i][n][1]=edge(n,0,inf);
vector<vector<int>> adj(n+1);
vector<int> dep(n+1);
for(int u=0;u<n;u++)adj[dp[i][u][0].to].emplace_back(u);
queue<int> q;
q.emplace(n);
dep[n]=0;
while(!q.empty()){
auto u=q.front();
q.pop();
int jump=dp[i][u][1].to;
int jump2=dp[i][jump][1].to;
bool ok=dep[u]-dep[jump]==dep[jump]-dep[jump2];
for(auto v:adj[u]){
dep[v]=dep[u]+1;
if(ok){
auto e=dp[i][v][0];
e=edge(e.to,e.add+dp[i][u][1].add,min(e.lim,dp[i][u][1].lim-e.add));
dp[i][v][1]=edge(e.to,e.add+dp[i][jump][1].add,min(e.lim,dp[i][jump][1].lim-e.add));
}else{
dp[i][v][1]=dp[i][v][0];
}
}
}
}
}
ll simulate(int x, int z){
int phase=0;
ll sz=1;
int cur=x;
ll val=z;
while(cur!=n){
if(val<S){
while(sz*2<=val){
sz*=2;
phase++;
}
while(cur!=n){
auto e=dp[phase][cur][1];
if(val>=e.lim)e=dp[phase][cur][0];
if(val>=e.lim)break;
val+=e.add;
cur=e.to;
}
}
if(val>=s[cur]){
val+=s[cur];
cur=w[cur];
}else{
val+=p[cur];
cur=l[cur];
}
}
return val;
}
