Given a weighted tree $T_0$, we define its diameter as the length of the longest path between two vertices on it, where the length of a path is equal to the sum of weights of edges in the path.
If the tree stretches like a spider or a yawning tiger, its diameter will change. Let's use $T_i$ to denote the state of the tree after $i$ seconds, at which time the weight of each edge has been increased by exactly $i$ units from $T_0$.
You will be presented with several different queries, and you should calculate the tree's diameter at some specified time for each query.
The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $60$.
For each test case, the first line contains two integers $n$ and $m$ indicating the number of vertices in the tree and the number of given queries respectively, where $2 <= n <= 2 times 10^5$ and $1 <= m <= 2 times 10^5$.
Each of the following $(n -1)$ lines contains three integers $u, v$ and $w$ which represent an edge in the original tree between the $u$-th vertex and the $v$-th one of weight $w$, where $1 <= u, v <= n$, $u != v$ and $1 <= w <= 10^8$.
Each of the following $m$ lines describes a query containing only one integer $k$ that asks you to calculate the diameter of the tree $T_k$, where $0 <= k <= 10^9$.
We guarantee that the sum of $n$ in all test cases is no larger than $10^6$, and the sum of $m$ in all test cases is no larger than $10^6$ as well.
For each test case, output a line containing "_Case #x:_" (without quotes) at first, where _x_ is the test case number starting from $1$.
Then output $m$ lines corresponding to all queries. The $i$-th line of them contains an integer indicating the answer to the $i$-th query.
In the second sample case:
## Input
The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $60$.For each test case, the first line contains two integers $n$ and $m$ indicating the number of vertices in the tree and the number of given queries respectively, where $2 <= n <= 2 times 10^5$ and $1 <= m <= 2 times 10^5$.Each of the following $(n -1)$ lines contains three integers $u, v$ and $w$ which represent an edge in the original tree between the $u$-th vertex and the $v$-th one of weight $w$, where $1 <= u, v <= n$, $u != v$ and $1 <= w <= 10^8$.Each of the following $m$ lines describes a query containing only one integer $k$ that asks you to calculate the diameter of the tree $T_k$, where $0 <= k <= 10^9$.We guarantee that the sum of $n$ in all test cases is no larger than $10^6$, and the sum of $m$ in all test cases is no larger than $10^6$ as well.
## Output
For each test case, output a line containing "_Case #x:_" (without quotes) at first, where _x_ is the test case number starting from $1$.Then output $m$ lines corresponding to all queries. The $i$-th line of them contains an integer indicating the answer to the $i$-th query.
[samples]
## Note
In the second sample case: the diameter of $T_0$ is $105$, which is the length of the path $1 -2 -3$; and the diameter of $T_5$ is $117$, which is the length of the path $1 -2 -4 -5$.
**Definitions**
Let $ W \in \mathbb{Z}^+ $ be the number of players, $ B \in \mathbb{Z}^+ $ the length of each sequence.
Let $ S = \{s_1, s_2, \dots, s_W\} $ be a set of $ W $ distinct binary strings over $ \{H, T\} $, each of length $ B $.
Let $ \mathcal{F} $ be the set of all infinite sequences of coin flips (each flip independently $ H $ or $ T $ with probability $ \frac{1}{2} $).
For each $ f \in \mathcal{F} $, define $ \tau(f) = \min \{ n \in \mathbb{N} \mid \exists i \in \{1,\dots,W\} \text{ s.t. } s_i \text{ appears as contiguous substring in } f_1 f_2 \dots f_n \} $.
**Constraints**
1. $ 1 \leq W \leq 10 $
2. $ 1 \leq B \leq 30 $
3. Each $ s_i \in \{H, T\}^B $
**Objective**
Compute the expected value:
$$
\mathbb{E}[\tau] = \sum_{f \in \mathcal{F}} \tau(f) \cdot \mathbb{P}(f)
$$
where $ \mathbb{P}(f) = 2^{-\tau(f)} $ for the prefix of $ f $ of length $ \tau(f) $, and the sum is over all finite prefixes that cause a match.