Dungeons Game

문제

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

The hero starts off entering dungeon $xx$, with strength $zz$. Every time the hero enters any dungeon $ii$ ($0\le i\le n-10\; \backslash le\; i\; \backslash le\; n\; -\; 1$), they confront opponent $ii$, and one of the following occurs:

• If the hero's strength is greater than or equal to the opponent's strength $s[i]s[i]$, the hero wins. This causes the hero's strength to increase by $s[i]s[i]$ ($s[i]\ge 1s[i]\; \backslash ge\; 1$). In this case the hero enters dungeon $w[i]w[i]$ next ($w[i]>iw[i]\; >\; i$).
• Otherwise, the hero loses. This causes the hero's strength to increase by $p[i]p[i]$ ($p[i]\ge 1p[i]\; \backslash ge\; 1$). In this case the hero enters dungeon $l[i]l[i]$ next.

Note $p[i]p[i]$ may be less than, equal to, or greater than $s[i]s[i]$. Also, $l[i]l[i]$ may be less than, equal to, or greater than $ii$. Regardless of the outcome of the confrontation, the opponent remains in dungeon $ii$ and maintains strength $s[i]s[i]$.

The game ends when the hero enters dungeon $nn$. One can show that the game ends after a finite number of confrontations, regardless of the hero's starting dungeon and strength.

Robert asked you to test his game by running $qq$ simulations. For each simulation, Robert defines a starting dungeon $xx$ and starting strength $zz$. Your task is to find out, for each simulation, the hero's strength when the game ends.