#include "dungeons.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
const ll MAXN = 4e5+100;
const ll MAXK = 24;
const ll INF = 1e18;
vector <int> s,p,w,l;
ll n;
struct TABLE{
struct path{
ll x,req,sum;
// < req
};
path sp[MAXK][MAXN];
void build(ll power){
for (ll i = 0;i < n;i ++){
if (s[i] > power)sp[0][i] = {l[i],s[i],p[i]};
else sp[0][i] = {w[i],INF,s[i]};
}
sp[0][n] = {n,INF,0};
for (ll j = 1;j < MAXK;j ++){
for (ll i = 0;i <= n;i ++){
sp[j][i].x = sp[j-1][sp[j-1][i].x].x;
sp[j][i].req = min(sp[j-1][i].req,sp[j-1][sp[j-1][i].x].req - sp[j-1][i].sum);
sp[j][i].sum = sp[j-1][i].sum + sp[j-1][sp[j-1][i].x].sum;
}
}
}
void eval(ll &x,ll &z){
for (ll j = MAXK-1;j >= 0;j --){
if (sp[j][x].req > z){
z += sp[j][x].sum;
x = sp[j][x].x;
}
}
if (x != n){
z += s[x];
x = w[x];
}
}
};
vector <ll> val;
vector <TABLE> a;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n=N;
s=S,p=P,w=W,l=L;
ll cur = 1;
val.push_back(cur);
while (cur < (10'000'000)){
cur = cur * 10;
val.push_back(cur);
}
a.resize(sz(val));
for (ll i = 0;i < sz(val);i ++)a[i].build(val[i]);
return;
}
long long simulate(int X, int Z) {
ll z=Z;
ll x=X;
ll ptr = 0;
while (x != n){
while (ptr + 1 < sz(val) && val[ptr+1] <= z)ptr++;
// cout<<val[ptr]<<endl;
a[ptr].eval(x,z);
}
return z;
}
