#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
int win[50005][24];//endpoint of win streak
ll stopwin[50005][24];//max on the range
ll winsum[50005][24];//sum of the win streak
ll lose[50005][24]; // endpoint of lose streak
ll stoplose[50005][24]; // min on the range
ll losesum[50005][24]; // sum of teh lose streak
int v[50005];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
for(int i = 0; i < n; ++i){
v[i] = s[i];
winsum[i][0] = s[i];
losesum[i][0] = p[i];
win[i][0] = w[i];
lose[i][0] = l[i];
if(w[i] == n){
stopwin[i][0] = 1e16;
}else
stopwin[i][0] = max(s[i] + s[i], s[w[i]]);
if(l[i] == n){
stoplose[i][0] = -1;
}else
stoplose[i][0] = min(s[i] + p[i], s[l[i]]);
}
win[n][0] = n;
lose[n][0] = n;
winsum[n][0] = 0;
losesum[n][0] = 0;
stopwin[n][0] = 1e16;
stoplose[n][0] = -1;
for(int j = 1; j < 24; ++j){
for(int i = 0; i < n; ++i){
win[i][j] = win[win[i][j-1]][j-1];
lose[i][j] = lose[lose[i][j-1]][j-1];
winsum[i][j] = winsum[i][j-1] + winsum[win[i][j-1]][j-1];
if(winsum[i][j] > 10000000000000000){
winsum[i][j] = 10000000000000000;
}
losesum[i][j] = losesum[i][j-1] + losesum[lose[i][j-1]][j-1];
if(losesum[i][j] > 10000000000000000){
losesum[i][j] = 10000000000000000;
}
stopwin[i][j] = max(stopwin[i][j-1] + winsum[win[i][j-1]][j-1], stopwin[win[i][j-1]][j-1]);
stoplose[i][j] = min(stoplose[i][j-1] + losesum[lose[i][j-1]][j-1], stoplose[lose[i][j-1]][j-1]);
}
}
return;
}
ll checkwin(int no, ll &s){
for(int i = 23; i >= 0; --i){
ll ns = s + winsum[no][i];
if(stopwin[no][i] > ns){
continue;
}
//cout << stopwin[no][i] << " ";
s += winsum[no][i];
no = win[no][i];
//cout << no << " " << s<< endl;
}
s += winsum[no][0];
return win[no][0];
}
ll checklose(int no, ll &s){
//cout << no << " " << s << endl;
for(int i = 23; i >= 0; --i){
ll ns = s + losesum[no][i];
//cout << stoplose[no][i] << " " << no << " " << ns << " " << i << endl;
if(stoplose[no][i] <= ns){
continue;
}
//cout << stoplose[no][i] << " ";
s += losesum[no][i];
no = lose[no][i];
//cout << no << " " << s << endl;
}
s += losesum[no][0];
//cout << lose[no][0] << " " << s << endl;
return lose[no][0];
}
long long simulate(int x, int z) {
//cout << stoplose[0][0] << " " << stoplose[1][1] << endl;
int no = x;
ll s = z;
bool parity = 0; //0 -> starts losing 1 -> starts winning
if(z >= v[x]){
parity = 1;
}
while(no != N){
//cout << no << endl;
// i get my new endpoint after the win/lose streak
//cout << parity << " " << no << " " << s << " im trying bro" << endl;
if(parity == 1){
no = checkwin(no, s);
parity = 0;
}else{
no = checklose(no, s);
parity = 1;
}
//cout << no << " " << s << endl;
}
return s;
}
