凛冬已至，长城已被摧毁。夜王（night king）和他的死亡军团现在控制了北方，他们袭击了除临冬城（Winterfell）以外的每一个地方，因为临冬城受到某种古老魔法的保护，免受死亡军团和异鬼（white walkers）的侵害。

北方可以表示为一棵有 $N$ 个节点的有向树（每个节点都有一个从 $1$ 到 $N$ 的唯一 ID），节点之间通过有向边连接，每条边代表一条路（路是单向的），每条路恰好有一个异鬼。树的根节点为 $1$，从根节点出发总是可以沿着某些路径到达任何其他节点。临冬城位于 ID 为 $v$ 的某个节点（不一定是根节点）。琼恩·雪诺（Jon Snow）和其余幸存者在临冬城听说夜王在某个 ID 范围在 $[L, R]$（包含 $L$ 和 $R$）内的节点中。琼恩知道，除非杀死夜王，否则他们无法赢得对抗异鬼的战争，因此他决定执行自杀式任务。

丹妮莉丝（Daenerys）、提利昂（Tyrion）和戴佛斯爵士（Sir Davos）试图劝阻他，但我们都知道琼恩的性格。当他们无法说服他时，提利昂提出了以下计划（给定 $v, L$ 和 $R$ 的值）：

• 琼恩和乔拉·莫尔蒙爵士（Sir Jorah Mormont）将执行此任务。
• 他们每个人都应该选择一个 ID 在 $[L, R]$ 范围内的节点，该节点可以从 $v$ 到达，并前往该节点。注意，他们不能选择同一个节点，但如果他们中有人选择了 $v$ 本身是可以的。
• 出于安全考虑，他们从 $v$ 到达所选节点的路径不应有任何共同的道路。
• 为了增加任务的收益，他们每个人都应该杀死他们所经过道路上的异鬼。

现在，给定 $v, L$ 和 $R$ 的一些可能场景，你能找到一对最优的节点，使他们杀死的异鬼总数最大化吗？

输入格式

程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个空格分隔的整数 $N$ ($1 \le N \le 20,000$) 和 $q$ ($1 \le q \le 10^5$)，分别表示节点数量和场景数量。

接下来一行包含 $N-1$ 个空格分隔的整数 $p_1, p_2, \dots, p_{N-1}$，表示存在一条从节点 $p_i$ 到节点 $i+1$ 的路。

接下来 $q$ 行，每行包含 3 个空格分隔的整数 $v, L$ 和 $R$ ($1 \le v, L, R \le N$)，表示一个场景（$L \le R$）。

输出格式

对于每个测试用例，打印 $q$ 行，每行包含对应场景的答案，即通过选择满足计划的最优节点对所能杀死的异鬼总数的最大值；如果找不到满足计划的不同节点对，则打印 -1。

样例

输入 1

1
6 4
1 2 2 3 4
2 5 6
1 2 6
2 1 3
2 1 2

输出 1

4
-1
1
-1

说明

在第一个场景中，一个人将前往节点 5，另一个人将前往节点 6，他们每个人都将杀死 2 个异鬼，所以总数是 4。

在第二个场景中，要到达该范围内的任何节点，他们必须经过从节点 1 到节点 2 的路，这根据计划是不允许的。

在第三个场景中，其中一人选择留在节点 2，另一人将前往节点 3。

在第四个场景中，他们无法从节点 2 到达节点 1（路的方向相反），并且他们不能同时选择节点 2。