题目描述

给定一棵有根树，根节点为 $1$。

对于每个节点 $u$，定义它的第 $k$ 级祖先为：从 $u$ 开始，沿着父边连续向上走 $k$ 次后到达的节点。

例如：

• 第 $0$ 级祖先就是它自己；
• 第 $1$ 级祖先是它的父节点；
• 如果向上走的过程中已经越过根节点，则答案记为 $0$。

现在有若干次询问，每次给出一个节点 $u$ 和一个非负整数 $k$，请你输出 $u$ 的第 $k$ 级祖先。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示树的节点数和询问次数。

第二行包含 $n-1$ 个整数，其中第 $i-1$ 个整数表示节点 $i$ 的父节点，适用于所有 $2 \le i \le n$。

接下来 $q$ 行，每行包含两个整数 $u$ 和 $k$，表示一次询问。

数据范围：

• $1 \le n, q \le 2 \times 10^5$
• 对于所有 $2 \le i \le n$，都有 $1 \le \mathrm{fa}_i < i$
• $1 \le u \le n$
• $0 \le k \le 10^{18}$

输出格式

对于每次询问，输出一行一个整数，表示答案。

7 6
1 1 2 2 3 3
4 1
4 2
4 3
7 2
1 0
1 1

2
1
0
1
1
0