#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int k = 20;
vector<vector<long long>>table;
vector<vector<long long>>nx;
vector<vector<long long>>bk;
vector<vector<long long>>sum;
vector<vector<long long>>bksum;
vector<vector<long long>>need;
vector<int>S,P,W,L;
long long N;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
table.resize(n,vector<long long>(k));
nx.resize(n,vector<long long>(k,-1));
sum.resize(n,vector<long long>(k,0));
need.resize(n,vector<long long>(k,1e16));
bk.resize(n,vector<long long>(k,-1));
bksum.resize(n,vector<long long>(k,0));
N = n;
S = s;
P = p;
W = w;
L = l;
for (long long i = 0;i<n;++i){
table[i][0] = s[i];
nx[i][0] = w[i];
sum[i][0] = s[i];
need[i][0] = s[i];
bk[i][0] = l[i];
bksum[i][0] = p[i];
}
for (long long i = 1;i<k;++i){
for (long long j = 0;j<n;++j){
if (nx[j][i - 1] == -1 || nx[j][i - 1] == n)continue;
//cout<<nx[j][i - 1]<<'\n';
nx[j][i] = nx[nx[j][i - 1]][i - 1];
table[j][i] = max(table[j][i - 1],table[nx[j][i - 1]][i - 1] - sum[j][i - 1]);
sum[j][i] = sum[j][i - 1] + sum[nx[j][i - 1]][i - 1];
}
}
for (long long i = 1;i<k;++i){
for (long long j = 0;j<n;++j){
if (bk[j][i - 1] == -1 || bk[j][i - 1] == n)continue;
//cout<<nx[j][i - 1]<<'\n';
bk[j][i] = bk[bk[j][i - 1]][i - 1];
need[j][i] = min(need[j][i - 1],need[bk[j][i - 1]][i - 1] - bksum[j][i - 1]);
bksum[j][i] = bksum[j][i - 1] + bksum[bk[j][i - 1]][i - 1];
}
}
return;
}
long long simulate(int x, int z) {
unordered_map<int,long long>mp;
long long Z = z;
int cnt = 0;
auto check = [&](int xx){
if (xx != N && mp.find(xx) != mp.end() && S[xx] > Z && Z != mp[xx]){
long long v = Z - mp[xx];
long long k = (S[xx] - Z + v - 1) / v;
Z+=k * v;
}
mp[xx] = Z;
};
while(x != N){
//check(x);
cnt++;
//assert(cnt < 50);
// cout<<x<<"->";
long long c = -1;
int left = 0,right = k - 1;
while(left <= right){
int mid = (left + right)>>1;
if (nx[x][mid] != -1 && table[x][mid] <= Z){
left = mid + 1;
c = mid;
}
else right = mid - 1;
}
++c;
//while(nx[x][c] != -1 && table[x][c] <= Z){
// ++c;
//}
if (c != 0){
Z+=sum[x][c - 1];
x = nx[x][c - 1];
}
check(x);
if (x != N && S[x] > Z){
int cc = 0;
while(bk[x][cc]!=-1 && need[x][cc] > Z){
++cc;
}
cc--;
while(cc >= 0 && x != N){
// cout<<x<<"->";
if (bk[x][cc] != -1){
if (need[x][cc] <= Z){
cc--;
}
else{
Z+=bksum[x][cc];
x = bk[x][cc];
//check(x);
}
}
else cc--;
}
//cout<<'\n';
}
}
// cout<<'\n';
return Z;
}
