던전 게임

Robert는 새로운 컴퓨터 게임을 설계하고 있다. 이 게임에는 영웅 한 명, 적 $n$명, 그리고 $n + 1$개의 던전이 있다. 적은 0부터 $n - 1$까지, 던전은 0부터 $n$까지 번호가 붙어 있다. 적 $i$ ($0 \le i \le n - 1$)는 던전 $i$에 있고 힘은 $s[i]$이다. 던전 $n$에는 적이 없다.

영웅은 힘 $z$를 가지고 던전 $x$에 들어가면서 시작한다. 영웅이 던전 $i$ ($0 \le i \le n - 1$)에 들어갈 때마다 적 $i$와 맞붙고, 다음 중 하나가 일어난다.

• 영웅의 힘이 적의 힘 $s[i]$ 이상이면 영웅이 이긴다. 영웅의 힘은 $s[i]$만큼 늘어난다 ($s[i] \ge 1$). 이때 영웅은 다음에 던전 $w[i]$에 들어간다 ($w[i] > i$).
• 그렇지 않으면 영웅이 진다. 영웅의 힘은 $p[i]$만큼 늘어난다 ($p[i] \ge 1$). 이때 영웅은 다음에 던전 $l[i]$에 들어간다.

$p[i]$는 $s[i]$보다 작을 수도, 같을 수도, 클 수도 있다. $l[i]$도 $i$보다 작거나 같거나 클 수 있다. 적은 결과와 관계없이 힘 $s[i]$를 유지한 채 던전 $i$에 남는다.

영웅이 던전 $n$에 들어가면 게임이 끝난다. 영웅이 어느 던전에서 어떤 힘으로 시작하든 게임은 유한한 횟수의 전투 후에 끝난다.

Robert는 $q$번의 시뮬레이션으로 이 게임을 테스트하려고 한다. 각 시뮬레이션은 시작 던전 $x$와 시작 힘 $z$를 준다. 각 시뮬레이션마다 게임이 끝났을 때 영웅의 힘을 구하라.

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