Dungeons Game

Robert is designing a new computer game. The game has one hero, $n$ opponents, and $n + 1$ dungeons. The opponents are numbered from $0$ to $n - 1$, and the dungeons are numbered from $0$ to $n$. Opponent $i$ ($0 \le i \le n - 1$) is in dungeon $i$ and has strength $s[i]$. Dungeon $n$ has no opponent.

The hero starts by entering dungeon $x$ with strength $z$. Each time the hero enters dungeon $i$ ($0 \le i \le n - 1$), the hero fights opponent $i$, and one of the following happens:

• If the hero's strength is at least $s[i]$, the hero wins. The hero's strength increases by $s[i]$ ($s[i] \ge 1$). The hero then enters dungeon $w[i]$ next ($w[i] > i$).
• Otherwise, the hero loses. The hero's strength increases by $p[i]$ ($p[i] \ge 1$). The hero then enters dungeon $l[i]$ next.

$p[i]$ may be less than, equal to, or greater than $s[i]$. $l[i]$ may also be less than, equal to, or greater than $i$. The opponent stays in dungeon $i$ with strength $s[i]$ regardless of the result.

The game ends when the hero enters dungeon $n$. The game ends after a finite number of fights no matter which dungeon and strength the hero starts with.

Robert wants to test the game with $q$ simulations. Each simulation gives a starting dungeon $x$ and a starting strength $z$. For each simulation, find the hero's strength when the game ends.

• $1 \le n \le 400\,000$
• $1 \le q \le 50\,000$
• $1 \le s[i], p[i] \le 10^7$ (for all $0 \le i \le n - 1$)
• $0 \le l[i], w[i] \le n$ (for all $0 \le i \le n - 1$)
• $w[i] > i$ (for all $0 \le i \le n - 1$)
• $0 \le x \le n - 1$
• $1 \le z \le 10^7$