题目内容

在一个大型组织中，员工从 1 到 n 编号，其中 1 号是最高负责人，没有上级。对于 $i>1$，员工 $i$ 有一位直接上级，记为 $a_i$。保证 $1 \le a_i < i$。 定义员工的 1 级上级为其直接上级，k 级上级（$k \ge 2$）为 k-1 级上级的直接上级。现在需要回答多次询问：员工 $x$ 的 k 级上级是谁？如果不存在，则视为 0。

约束：员工总数 $n$ 和询问次数 $q$ 均不超过 50000。对于 $i>1$，直接上级 $a_i$ 满足 $1 \le a_i < i$。每次询问中的 $x$ 和 $k$ 满足 $1 \le x, k \le n$。

输入描述

第一行包含两个整数 $n$ 和 $q$，表示员工总数与询问次数。 第二行包含 $n-1$ 个整数 $a_2, a_3, \dots, a_n$ ($1 \le a_i < i$)，分别表示员工 2 到员工 n 的直接上级编号。 接下来 $q$ 行，每行包含两个整数 $x$ 和 $k$ ($1 \le x, k \le n$)，表示询问员工 $x$ 的 k 级上级。

输出描述

输出共 $q$ 行，每行一个整数，表示对应询问的 k 级上级编号。若不存在该上级，则输出 0。

样例1

输入

6 4
1 1 2 2 5
4 1
6 2
6 3
3 2

输出

2
2
1
0

说明

组织共有 $n=6$ 名员工，上级关系如下：员工 1 是根；员工 2 和 3 的直接上级均为 1；员工 4 和 5 的直接上级均为 2；员工 6 的直接上级为 5。

• 查询员工 4 的 1 级上级：直接上级为 2，输出 2。
• 查询员工 6 的 2 级上级：6 的直接上级是 5，5 的直接上级是 2，因此 2 级上级为 2。
• 查询员工 6 的 3 级上级：2 级上级为 2，2 的直接上级为 1，因此 3 级上级为 1。
• 查询员工 3 的 2 级上级：3 的直接上级是 1，1 没有上级，因此 2 级上级不存在，输出 0。

样例2

输入

2 3
1
2 1
2 2
1 1

输出

1
0
0

说明

边界情况，只有 $n=2$ 名员工。员工 1 是最高负责人，员工 2 的直接上级是 1。

• 查询员工 2 的 1 级上级：直接上级为 1，输出 1。
• 查询员工 2 的 2 级上级：2 向上 1 级为 1，而 1 没有上级，因此输出 0。
• 查询员工 1 的 1 级上级：根节点无上级，直接输出 0。

样例3

输入

5 3
1 2 3 4
5 2
5 5
4 3

输出

3
0
1

说明

组织为一条链：1 $\leftarrow$ 2 $\leftarrow$ 3 $\leftarrow$ 4 $\leftarrow$ 5。

• 查询员工 5 的 2 级上级：向上 1 级为 4，向上 2 级为 3。
• 查询员工 5 的 5 级上级：从 5 到根 1 的深度为 4，因此 5 级上级不存在，输出 0。
• 查询员工 4 的 3 级上级：向上 1 级为 3，2 级为 2，3 级为 1，输出 1。