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

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 ≤ 105, −105 ≤ L ≤ 105)— 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 /= v, −105 ≤ w ≤ 105) . 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.

ouput

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.

Example

Input：

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

ouput：

9
1
0
0