#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
long long j[12][12][400001][3];
long long inf;
int n;
int s[400001];
int p[400001];
int w[400001];
int l[400001];
int g[10000001];
int k = 12;
int blog = 4;
vector<long long> t;
void init(int nt,vector<int> st,vector<int> pt,vector<int> wt,vector<int> lt)
{
inf = 1e18;
n = nt;
for(int i =0 ;i<n;i++)
{
s[i] = st[i];
p[i] = pt[i];
w[i] = wt[i];
l[i] = lt[i];
}
s[n] = 0;
p[n] = 0;
w[n] = n;
l[n] = n;
for(int i = 0;i<k;i++)
{
for(int q = 0;q<n;q++)
{
if(s[q] < (1<<i))
{
j[i][0][q][0] = w[q];
j[i][0][q][1] = inf;
j[i][0][q][2] = s[q];
}
else
{
j[i][0][q][0] = l[q];
j[i][0][q][1] = s[q];
j[i][0][q][2] = p[q];
}
}
j[i][0][n][0] = n;
j[i][0][n][1] = inf;
j[i][0][n][2] = 0;
}
for(int i = 0;i<k;i++)
{
for(int w = 1;w<k;w++)
{
for(int q= 0;q<=n;q++)
{
j[i][w][q][0] = j[i][w-1][j[i][w-1][q][0]][0];
j[i][w][q][1] = min(j[i][w-1][q][1],j[i][w-1][j[i][w-1][q][0]][1]-j[i][w-1][q][2]); j[i][w][q][2] = j[i][w-1][q][2] + j[i][w-1][j[i][w-1][q][0]][2];
j[i][w][q][2] = j[i][w-1][q][2] + j[i][w-1][j[i][w-1][q][0]][2];
}
}
}
/*for(int i = 0;i<k;i++)
{
for(int w = 0;w<k;w++)
{
for(int q =0;q<=n;q++)
{
cerr<<j[i][w][q][0]<<" "<<j[i][w][q][1]<<" "<<j[i][w][q][2]<<"\n";
}
cerr<<"\n";
}
cerr<<"\n";
}*/
}
long long simulate(int x,int zt)
{
long long z = zt;
for(int i = 0;i<k;i++)
{
for(int r = 0;r<blog-1;r++)
{
for(int w = k-1;w>=0;w--)
{
if(j[i][w][x][1] > z && j[i][w][x][2]+z < (1<<(i+1)))
{
z += j[i][w][x][2];
x = j[i][w][x][0];
}
/*if(i == 9 && r == 0)
{
cerr<<x<<" "<<z<<"\n";
}*/
}
if(z < (1<<(i+1)))
{
if(z < s[x])
{
z+= p[x];
x = l[x];
}
else
{
z+=s[x];
x = w[x];
}
}
//cerr<<i<<" "<<(1<<i)<<" "<<r<<" "<<z<<" "<<x<<"\n";
}
//cerr<<"\n";
}
//cerr<<"\n";
return z;
}
