Mirko has a large house consisting of $N$ rooms connected by $N-1$ corridors. Each corridor connects two different rooms, and all rooms are interconnected. Each corridor is 1 meter long. Mirko often cleans the rooms in the apartment but rarely the corridors. Dust has accumulated in the corridors, and Mirko now wants to vacuum them.

Unfortunately, every vacuum cleaner has a cord of limited length. Each room has a power outlet, and the vacuum cleaner must be plugged into an outlet in some room to operate. Mirko starts from room 1 and can perform the following actions:

If the vacuum cleaner is not plugged into power, he can: Plug it into the room where he is currently located. Pick up the vacuum cleaner and move to one of the adjacent rooms. Passing through a corridor takes 1 minute.

If the vacuum cleaner is plugged into power, he can: If he is in the room where the vacuum cleaner is plugged in, he can unplug it from the outlet. Move to one of the adjacent rooms while vacuuming the corridor on the way. He can only do this if the cord is long enough. That is, if the distance between the room where the vacuum cleaner is plugged in and the target room is less than or equal to the length of the cord. Cleaning a corridor takes 1 minute.

Mirko's vacuum cleaner has broken! Now he is at a store where there are $Q$ vacuum cleaners, the $i$-th of which has a cord length of $r_i$ meters. He is interested in knowing, for each vacuum cleaner, the minimum time required to vacuum all the corridors if he buys that vacuum cleaner. Help him determine these times!

Input

The first line contains the natural numbers $N$ and $Q$, the number of rooms and the number of vacuum cleaners.

The next $N-1$ lines contain the natural numbers $x_i$ and $y_i$ ($1 \le x_i, y_i \le N, x_i \neq y_i$), which indicate that there is a corridor between rooms $x_i$ and $y_i$.

The last line contains $Q$ numbers $r_i$ ($1 \le r_i \le N$), the cord lengths of the vacuum cleaners.

Output

In a single line, print $Q$ numbers where the $i$-th number represents the minimum cleaning time with the $i$-th vacuum cleaner.

Subtasks

In all subtasks, $2 \le N \le 3 \cdot 10^5$ and $1 \le Q \le 3 \cdot 10^5$.

Examples

Input 1

5 2
1 2
2 3
3 4
4 5
2 5
8 4

Output 1

8 4

Note 1

One way Mirko can most quickly vacuum all corridors with a cord length of 2m is as follows: Walk from room 1 to room 3. (2 minutes) Plug the vacuum cleaner into room 3. Vacuum the corridors between rooms 3 and 4, and 4 and 5 (2 minutes). Return to room 3. (2 minutes) * Vacuum the corridors between rooms 3 and 2, and 2 and 1 (2 minutes). All corridors are now cleaned.

Input 2

10 2
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10
1 3

Output 2

24 16

Input 3

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

Output 3

6 12