题目描述

有一座神秘的城堡，里面共有 $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$ 行，每行一个整数，表示对应探险者最终所在的密室编号。

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

3
2
4

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

2
3
7
8
3

提示

【样例 $1$ 解释】

从 $1$ 号密室出发，传送 $2$ 次：$1\to 2\to 3$；

从 $2$ 号密室出发，传送 $3$ 次：$2\to 3\to 4\to 2$；

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

【数据范围】

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