Dungeon Simulation

Robert is designing a new computer game. In this game, there is one hero, n enemies and n+1 dungeons. The enemies are numbered from 0 to n-1, and the dungeons are numbered from 0 to n. Enemy i (where \(0 \le i \le n-1\)) is located in dungeon i and has a strength of \(s[i]\). Note that dungeon \(n\) contains no enemy.

The hero starts the game in dungeon \(x\) with an initial ability of \(z\). Whenever the hero enters a dungeon \(i\) (where \(0 \le i \le n-1\)), he faces enemy i and one of the following occurs:

• If the hero's ability is greater than or equal to the enemy's strength, i.e. \(z \ge s[i]\), the hero wins. In doing so, his ability increases by \(s[i]\) (\(s[i]\ge 1\)), and he proceeds to dungeon \(w[i]\) where \(w[i] > i\).
• If the hero's ability is less than \(s[i]\), he loses. In this case, his ability increases by \(p[i]\) (\(p[i]\ge 1\)), and he moves to dungeon \(l[i]\). Note that \(p[i]\) could be less than, equal to, or greater than \(s[i]\), and \(l[i]\) may be less than, equal to, or greater than \(i\).

No matter the outcome, enemy i remains in dungeon i with strength \(s[i]\). The game ends once the hero enters dungeon \(n\). It is guaranteed that the game will terminate after a finite number of battles regardless of the hero's starting dungeon or ability.

Robert will run \(q\) simulations. For each simulation, he provides the hero's starting dungeon \(x\) and initial ability \(z\). Your task is to compute the hero's final ability when the game ends.

inputFormat

The input is given as follows:

1. An integer \(n\) representing the number of enemies (and there are \(n+1\) dungeons).
2. A line containing \(n\) integers: \(s[0], s[1], \ldots, s[n-1]\), the strengths of the enemies.
3. A line containing \(n\) integers: \(w[0], w[1], \ldots, w[n-1]\) where each \(w[i] > i\) is the next dungeon if the hero wins against enemy \(i\).
4. A line containing \(n\) integers: \(p[0], p[1], \ldots, p[n-1]\), the ability increase when the hero loses against enemy \(i\).
5. A line containing \(n\) integers: \(l[0], l[1], \ldots, l[n-1]\), the next dungeon when the hero loses against enemy \(i\).
6. An integer \(q\) representing the number of simulations.
7. Then \(q\) lines follow, each containing two integers \(x\) and \(z\) representing the starting dungeon and the hero's initial ability for that simulation.

outputFormat

For each simulation, output a single integer representing the final ability of the hero when the game ends (i.e. when the hero enters dungeon \(n\)).

sample

3
5 10 20
1 3 3
3 4 5
0 0 0
3
0 5
0 4
1 9

20
22
28