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

Input

The input consists of multiple test cases. The first line contains a single integer $T$($1 \le T \le 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 \le n \le 10^5$, $−10^5 \le L \le 10^5$) — the number of nodes in the tree.

Each of the next $n − 1$ lines contains three integers $u$, $v$, $w$ ($1 \le u, v \le n$, $u \ne v$, $−10^5 \le w \le 10^5$).

The next line contains a positive integer $Q$ ($1 \le Q \le 10$).

Each of the next $Q$ lines contains one integer $p$ ($1 \le p \le 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.

Example

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

9
1
0
0

Limitation

Time limit: 8 seconds

Memory limit: 512 megabytes