Alice 目前被困在一个迷宫中，这个迷宫可以看作一棵树。树上的每条边都有一个权重，代表该边的长度。树的叶子节点代表出口，当 Alice 到达一个叶子节点时，意味着她已成功逃离迷宫。

叶子节点定义为度数为 1 且不是根节点的节点。

每个迷宫都有一个难度等级，记为 $L$。当 Alice 位于树中的节点 $x$ 时，她可以选择跳跃到她子树中的某个节点 $y$。设 $s$ 为从 $x$ 到 $y$ 的路径上所有边权之和。从 $x$ 跳跃到 $y$ 所消耗的能量为 $(s - L)^2$。

Alice 想知道，如果以 $p$ 为根节点且她从 $p$ 出发，逃离迷宫所需的最少能量是多少。Alice 总共会询问 $Q$ 次。

数据保证对于任意给定的点对 $x$ 和 $y$，它们之间路径上的边权和 $s$ 的绝对值不超过 $10^9$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, L$ ($3 \le n \le 10^5, -10^5 \le L \le 10^5$)，表示树中的节点数。

接下来的 $n - 1$ 行，每行包含三个整数 $u, v, w$ ($1 \le u, v \le n, u \neq v, -10^5 \le w \le 10^5$)。

下一行包含一个正整数 $Q$ ($1 \le Q \le 10$)。

接下来的 $Q$ 行，每行包含一个整数 $p$ ($1 \le p \le n$)，询问以 $p$ 为根节点且从 $p$ 出发时，逃离迷宫所需的最少能量。

保证给定的图是一棵树。

输出格式

对于每个测试用例，输出 $Q$ 行。每行包含一个整数，表示所需的最少能量。

数据保证答案不会超过 64 位有符号整数的表示范围。

样例

输入 1

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

输出 1

9
1
0
0