Petya 有一个有根树,每个顶点上都写有一个整数。顶点 $$$1$$$ 是根。你要回答一些关于这棵树的问题。
树是没有循环的连通图。有根树有一个特殊的顶点,称为根。节点 $$$v$$$ 的父节点是从 $$$v$$$ 到根的最短路径上的下一个顶点。
每个问题由三个整数 $$$v$$$、$$$l$$$ 和 $$$k$$$ 定义。要获得问题的答案,您需要执行以下步骤:
- 首先,记下从顶点$$$v$$$到根的最短路径上写入的所有整数的序列(包括$$$v$$$和根中写入的整数)。
- 计算每个整数出现的次数。删除出现次数少于 $$$l$$$ 的所有整数。
- 替换序列,删除所有重复项并按原始列表中出现的次数按升序对元素进行排序。如果出现平局,您可以任意选择这些元素的顺序。
- 问题的答案是剩余序列中的第 $$$k$$$ 个数字。请注意,答案并不总是唯一确定的,因为可能有多个顺序。此外,此步骤的序列长度可能小于 $$$k$$$,在这种情况下答案是 $$$-1$$$。
例如,如果从 $$$v$$$ 到根的路径上的整数序列为 $$$[2, 2, 1, 7, 1, 1, 4, 4, 4, 4]$$$、$$$l = 2$$$ 和 $$$k = 2$$$,则答案为 $$$1$$$。
请回答有关树的所有问题。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^6$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \leq n, q \leq 10^6$$$) — 树中的顶点数和问题数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$),其中 $$$a_i$$$ 是写在第 $$$i$$$ 个顶点上的数字。
第三行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$),其中 $$$p_i$$$ 是节点 $$$i$$$ 的父节点。保证值 $$$p$$$ 定义正确的树。
接下来的 $$$q$$$ 行包含三个整数 $$$v$$$, $$$l$$$, $$$k$$$ ($$$1 \leq v, l, k \leq n$$$) — 问题的描述。
保证所有测试用例的 $$$n$$$ 总和和 $$$q$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例的每个问题,打印问题的答案。如果有多个答案,请打印其中一个。
示例
输入 #1
2 3 3 1 1 1 1 2 3 1 1 3 1 2 3 2 1 5 5 1 2 1 1 2 1 1 2 2 3 1 1 2 1 2 4 1 1 4 2 1 4 2 2
输出 #1
1 -1 1 1 1 2 1 -1