该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Alice is currently trapped in a maze, which can be seen as a tree. Each edge in the tree has a weight representing the length of that edge. The leaves of the tree represent the exits, and when Alice reaches a leaf, it means she has successfully escaped from the maze. A leaf is defined as a node with degree 1 that is not the root. Each maze has a difficulty level, denoted as L. When Alice is at a node x in the tree, she can choose to jump to a node y in her subtree. Let s be the sum of the edge weights along the path from x to y. The energy spent when jumping from x to y is$(s − L) ^2$. Alice wants to know the minimum amount of energy required to escape the maze if the tree has p as the root and she starts from p. Alice will ask this question a total of Q times. The data guarantees that for any given pair of points x and y, the absolute value of the sum of edge weights s along the path between them does not exceed $10^9$ .

Format

Input

The input consists of multiple test cases. The first line contains a single integer T(1 ≤ T ≤ 5) — the number of test cases. Description of the test cases follows. The first line of each test case contains two integers n, L ($3 ≤ n ≤ 10^5 , −10^5 ≤ L ≤ 10^5$ )— the number of nodes in the tree. Each of the next n − 1 lines contains three integers u, v, w ($1 ≤ u, v ≤ n, u \neq v, −10^5 ≤ w ≤ 10^5$) . The next line contains a positive integer Q (1 ≤ Q ≤ 10). Each of the next $Q$ lines contains one integer p (1 ≤ p ≤ n) asks the minimum amount of energy required to escape the maze if the tree has p as the root and she starts from p. It is guaranteed that the given graph is a tree.

Output

For each test case, output Q lines. Each line should contain a integer indicating the minimum amount of energy required. The data guarantees that the answer will not exceed the range that can be represented by a 64-bit signed integer.

Samples

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

9 
1 
0 
0

Limitation

8s, 512mb for each test case.