该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

城堡探险

题目描述

有一座神秘的城堡，里面共有 $n$ 间密室，编号为 $1$ 到 $n$。

每间密室的墙壁上都刻着一个符文，符文上写着一个数字 $a_i$（表示从第 $i$ 间密室出发，会被传送到第 $a_i$ 间密室，有可能 $a_i=i$，即传送到自己）。

现在有 $m$ 位探险者前来挑战，每位探险者的探险过程如下：

1. 从某间密室 $x$ 出发；
2. 连续进行 $y$ 次传送，每次传送都严格按照当前密室符文上指示的目标移动。

每位探险者都想知道：自己最终会停留在哪一间密室？

请你编写程序，帮助所有探险者快速得到答案。

输入格式

第一行两个整数 $n, m$，分别表示密室的数量和探险者的数量。 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个密室的符文数字。 接下来 $m$ 行，每行两个整数 $x, y$，表示一位探险者的起点和传送次数。

输出格式

共 $m$ 行，每行一个整数，表示对应探险者最终所在的密室编号。

样例

4 3
2 3 4 2
1 2
2 3
1 9

3
2
4

从 1 号密室出发，传送 2 次：1 → 2 → 3； 从 2 号密室出发，传送 3 次：2 → 3 → 4 → 2； 从 1 号密室出发，传送 9 次：1 → 2 → 3 → 4 → 2 → 3 → 4 → 2 → 3 → 4。

8 5
2 3 4 5 1 7 8 6
1 1
1 2
6 4
7 100000000
3 100000000

2
3
7
8
3

数据范围

$1 \le n, m \le 2\times 10^5$，$0 \le y \le 10^9$，$1 \le a_i, x \le n$