文件输入输出

本题采用文件输入输出。

• 输入文件：explore.in
• 输出文件：explore.out

题目描述

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

每间密室的墙壁上都刻着一个符文，第 $i$ 间密室的符文上写着数字 $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\to2\to3$；
• 从 $2$ 号密室出发，传送 $3$ 次：$2\to3\to4\to2$；
• 从 $1$ 号密室出发，传送 $9$ 次：$1\to2\to3\to4\to2\to3\to4\to2\to3\to4$。

样例输入 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$。