#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
const int maxn = 4e5 + 10;
const int logn = 31;
pll pai[2][logn][maxn];
int N, S;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
S = s[0];
N = n;
for( int i = 0; i < logn; i++ ){
for( int j = 0; j < n; j++ ){
if( i == 0 ) pai[0][0][j] = pll( l[j], p[j] );
else{
auto [a, va] = pai[0][i - 1][j];
auto [b, vb] = pai[0][i - 1][a];
pai[0][i][j] = pll( b, va + vb );
}
}
pai[0][i][n] = pll( n, 0 );
}
for( int i = 0; i < logn; i++ ){
for( int j = 0; j < n; j++ ){
if( i == 0 ) pai[1][0][j] = pll( w[j], s[j] );
else{
auto [a, va] = pai[1][i - 1][j];
auto [b, vb] = pai[1][i - 1][a];
pai[1][i][j] = pll( b, va + vb );
}
}
pai[1][i][n] = pll( n, 0 );
}
return;
}
pll lift( int id, ll val, int t ){
if( t == 0 ){
if( val >= S ) return pll( id, val );
for( int i = logn - 1; i >= 0; i-- ){
if( val + pai[t][i][id].second < S ){
val += pai[t][i][id].second;
id = pai[t][i][id].first;
}
}
val += pai[t][0][id].second;
id = pai[t][0][id].first;
return pll( id, val );
}
else{
for( int i = logn - 1; i >= 0; i-- ){
if( pai[t][i][id].first < N ){
val += pai[t][i][id].second;
id = pai[t][i][id].first;
}
}
val += pai[t][0][id].second;
id = pai[t][0][id].first;
return pll( id, val );
}
}
long long simulate( int x, int z ) {
auto [a, va] = lift( x, z, 0 );
return lift( a, va, 1 ).second;
}
