You are given a tree with colored edges.

A path is defined as valid if the colors of the edges on the path appear only on that specific path.

You are given $m$ independent queries. Each query asks for the maximum length of a valid path after removing a specific vertex.

A path is still valid if it was valid in the original tree and the removed vertex is not on the path.

Input

The first line contains two integers $n$ and $m$.

The next $n-1$ lines each contain three integers $x, y, col$, representing an edge between $x$ and $y$ with color $col$.

The next $m$ lines each contain an integer $x$, representing a query.

Output

Output $m$ lines, each containing an integer representing the answer to the corresponding query.

Constraints

$m \le n \le 10^5, 1 \le x, y, col \le n$

Subtask 1 (9 points): $n \le 100$.

Subtask 2 (11 points): $n \le 1000$.

Subtask 3 (17 points): The tree structure is guaranteed to be a chain.

Subtask 4 (23 points): $m = 1$.

Subtask 5 (40 points): No additional constraints.

Examples

Input 1

4 4
1 2 2
1 3 1
1 4 1
1
2
3
4

Output 1

0
2
1
1