题目描述

每个测试的时间限制：3 秒
每个测试的内存限制：256 兆字节

在这个问题中，你需要帮助伯兰军队组织他们的指挥传递系统。

伯兰军队中有 $n$ 名军官。第一名军官是军队的指挥官，他没有上级。其他每名军官恰好有一名直属上级。如果军官 $a$ 是军官 $b$ 的直属上级，那么也可以说军官 $b$ 是军官 $a$ 的直属下属。

如果满足以下条件之一，则称军官 $x$ 是军官 $y$ 的下属（直接或间接）：

• 军官 $y$ 是军官 $x$ 的直属上级；
• 军官 $x$ 的直属上级是军官 $y$ 的下属。

例如，在下图中，军官 $3$ 的下属有：$5, 6, 7, 8, 9$。

伯兰军队的组织结构是：除了指挥官外，每名军官都是指挥官的下属。

正式地，我们将伯兰军队表示为一棵有 $n$ 个顶点的树，其中顶点 $u$ 对应军官 $u$。顶点 $u$ 的父节点对应军官 $u$ 的直属上级。根节点（索引为 $1$）对应军队指挥官。

伯兰战争部命令你回答 $q$ 个查询，第 $i$ 个查询的形式为 $(u_i, k_i)$，其中 $u_i$ 是某名军官，$k_i$ 是一个正整数。

处理第 $i$ 个查询时，想象一个命令从 $u_i$ 向其下属传播。这里使用典型的 DFS（深度优先搜索）算法。

假设当前军官是 $a$，他正在传播命令。军官 $a$ 选择一名尚未收到此命令的直属下属（即树中的一个子节点）$b$。如果有多个这样的直属下属，则 $a$ 选择索引最小的那个。军官 $a$ 将命令传给军官 $b$。之后，$b$ 使用相同的算法将其命令传播到其子树。当 $b$ 完成命令传播后，军官 $a$ 再选择下一个直属下属（使用相同的策略）。当军官 $a$ 无法选择任何尚未收到命令的直属下属时，军官 $a$ 完成命令传播。

请看下面的例子：

如果军官 $1$ 传播命令，军官按以下顺序收到命令：$[1,2,3,5,6,8,7,9,4]$。

如果军官 $3$ 传播命令，军官按以下顺序收到命令：$[3,5,6,8,7,9]$。

如果军官 $7$ 传播命令，军官按以下顺序收到命令：$[7,9]$。

如果军官 $9$ 传播命令，军官按以下顺序收到命令：$[9]$。

要回答第 $i$ 个查询 $(u_i, k_i)$，需要构造一个序列，描述如果第 $u_i$ 名军官传播命令时，军官收到命令的顺序。返回构造列表中的第 $k_i$ 个元素，如果元素少于 $k_i$ 个，则返回 $-1$。

你应该独立处理查询。查询不会影响后续查询。

输入格式

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 2 \cdot 10^5$，$1 \le q \le 2 \cdot 10^5$）—— 伯兰军队的军官人数和查询次数。

第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \le p_i < i$），其中 $p_i$ 是索引为 $i$ 的军官的直属上级的索引。指挥官索引为 $1$，他没有上级。

接下来 $q$ 行描述查询。第 $i$ 个查询由一对整数 $(u_i, k_i)$ 给出（$1 \le u_i, k_i \le n$），其中 $u_i$ 是开始传播命令的军官索引，$k_i$ 是指令传播序列中所需军官的位置。

输出格式

输出 $q$ 行，其中第 $i$ 行是如果命令从军官 $u_i$ 开始传播时，列表中第 $k_i$ 个位置的军官编号。如果收到命令的军官人数少于 $k_i$，则输出 -1。

你应该独立处理查询。它们不会相互影响。

9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9

3
6
8
-1
9
4