题目背景

给定一棵有根树，你需要回答若干次询问：某个节点的第 $k$ 个祖先是谁。

题目描述

给你一棵有 $n$ 个节点的有根树，节点编号为 $0 \sim n-1$，根节点为 $0$ 号节点。

树以父节点数组的形式给出：第 $i$ 个节点（$1 \le i \le n-1$）的父节点为 $p_i$。

定义节点 $u$ 的第 $k$ 个祖先为：从 $u$ 出发，沿父节点方向向上走 $k$ 步到达的节点。节点 $u$ 的第 $1$ 个祖先是它的父节点，第 $2$ 个祖先是父节点的父节点，以此类推。根节点没有祖先。

接下来有 $m$ 次询问，每次询问给出 $u$ 和 $k$，请输出节点 $u$ 的第 $k$ 个祖先的编号；如果该祖先不存在（即向上走不到 $k$ 步就越过了根节点），输出 $-1$。

输入格式

第一行两个整数 $n, m$，表示节点个数和询问次数。

第二行 $n-1$ 个整数 $p_1, p_2, \dots, p_{n-1}$，其中 $p_i$ 表示节点 $i$ 的父节点编号。保证 $0 \le p_i < i$。当 $n=1$ 时，本行为空行。

接下来 $m$ 行，每行两个整数 $u, k$，表示一次询问。

输出格式

输出 $m$ 行，每行一个整数，依次表示每次询问的答案：节点 $u$ 的第 $k$ 个祖先的编号，不存在则输出 $-1$。

样例

7 3
0 0 1 1 2 2
3 1
5 2
6 3

1
0
-1

样例解释

树的结构为：节点 $1,2$ 的父节点是 $0$；节点 $3,4$ 的父节点是 $1$；节点 $5,6$ 的父节点是 $2$。

• 询问 $1$：节点 $3$ 向上走 $1$ 步到达节点 $1$。
• 询问 $2$：节点 $5$ 向上走 $2$ 步，依次经过节点 $2$，到达节点 $0$。
• 询问 $3$：节点 $6$ 向上走 $3$ 步会越过根节点，祖先不存在，输出 $-1$。

数据范围

对于 $100\%$ 的数据，保证：

• $1 \le n \le 5 \times 10^4$
• $1 \le m \le 10^5$
• $0 \le p_i < i$
• $0 \le u \le n-1$
• $1 \le k \le n$