CF1591E.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.

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