CF1585E.Frequency Queries

Petya has a rooted tree with an integer written on each vertex. The vertex $1$ is the root. You are to answer some questions about the tree.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a node $v$ is the next vertex on the shortest path from $v$ to the root.

Each question is defined by three integers $v$, $l$, and $k$. To get the answer to the question, you need to perform the following steps:

• First, write down the sequence of all integers written on the shortest path from the vertex $v$ to the root (including those written in the $v$ and the root).
• Count the number of times each integer occurs. Remove all integers with less than $l$ occurrences.
• Replace the sequence, removing all duplicates and ordering the elements by the number of occurrences in the original list in increasing order. In case of a tie, you can choose the order of these elements arbitrary.
• The answer to the question is the $k$-th number in the remaining sequence. Note that the answer is not always uniquely determined, because there could be several orderings. Also, it is possible that the length of the sequence on this step is less than $k$, in this case the answer is $-1$.

For example, if the sequence of integers on the path from $v$ to the root is $[2, 2, 1, 7, 1, 1, 4, 4, 4, 4]$, $l = 2$ and $k = 2$, then the answer is $1$.

Please answer all questions about the tree.

佩蒂亚有一棵有根树，每个顶点上写有一个整数。顶点 $1$ 为根节点。你需要回答关于这棵树的一些查询。

树是一种无环的连通图。有根树具有一个特殊的顶点，称为根节点。节点 $v$ 的父节点是指从 $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$。

请回答关于该树的所有查询。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^6$). Description of the test cases follows.

The first line of each test case contains two integers $n$, $q$ ($1 \leq n, q \leq 10^6$) — the number of vertices in the tree and the number of questions.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$), where $a_i$ is the number written on the $i$-th vertex.

The third line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \leq p_i \leq n$), where $p_i$ is the parent of node $i$. It's guaranteed that the values $p$ define a correct tree.

Each of the next $q$ lines contains three integers $v$, $l$, $k$ ($1 \leq v, l, k \leq n$) — descriptions of questions.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each question of each test case print the answer to the question. In case of multiple answers, print any.

对于每个测试用例的每个问题，请输出该问题的答案。若存在多个正确答案，输出任意一个即可。