#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
const long long INF = (long long)1e18;
const int logn = 25, bont = 7, M = 4;
struct adat{
int ind;
long long legk, ossz;
adat() {}
adat(int ind, long long legk, long long ossz) : ind(ind), legk(legk), ossz(ossz) {}
};
inline adat merge(adat a, adat b){
return adat(b.ind, min(a.legk, b.legk-a.ossz), a.ossz+b.ossz);
}
vector<vector<vector<adat>>> st;
vector<int> s, p, w, l;
int n;
void calcST(vector<vector<adat>> &v, int k){
v.resize(n, vector<adat>(logn));
for(int i = 0; i < n; i++){
if(s[i] <= k)
v[i][0] = adat(w[i], INF, s[i]);
else
v[i][0] = adat(l[i], s[i], p[i]);
}
for(int j = 1; j < logn; j++)
for(int i = 0; i < n; i++)
v[i][j] = merge(v[i][j-1], v[v[i][j-1].ind][j-1]);
}
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;
s.push_back(0);
p.push_back(0);
w.push_back(n);
l.push_back(n);
++n;
st.resize(bont);
for(int i = 0; i < bont; i++)
calcST(st[i], 1<<(i*M));
return;
}
long long simulate(int x, int z) {
int y = 0;
long long ert = z;
while (x != n-1)
{
while (y+1 < bont && 1ll<<((y+1)*M) <= ert)
++y;
for(int i = logn-1; i >= 0; i--){
if(st[y][x][i].legk > ert){
ert += st[y][x][i].ossz;
x = st[y][x][i].ind;
}
}
ert += (long long)s[x];
x = w[x];
}
return ert;
}
