Problem Description

城堡探险（explore）

【问题描述】

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

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

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

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

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

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

【输入格式】

第一行两个整数 $n, m$，分别表示密室的数量和探险者的数量。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个密室的符文数字。

接下来 $m$ 行，每行两个整数 $x, y$，表示一位探险者的起点和传送次数。

【输出格式】

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

【样例1输入】

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

【样例1输出】

3
2
4

【样例1解释】

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

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

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

【样例2输入】

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

【样例2输出】

2
3
7
8
3

【数据范围】

对于所有的数据，保证：$1 \le n, m \le 10^5$；$1 \le a_i \le n$；$1 \le x \le n$；$0 \le y \le 10^9$。

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

3
2
4

Source

2026年山东省信息学体验营