Mirko 拥有一栋大房子，由 $N$ 个房间和 $N-1$ 条走廊组成。每条走廊连接两个不同的房间，且所有房间都是连通的。每条走廊的长度为 $1$ 米。Mirko 经常打扫房间，但很少打扫走廊。走廊里积满了灰尘，Mirko 现在想要清扫它们。

每个吸尘器都有一个有限长度的电缆。每个房间都有一个插座，吸尘器必须插在某个房间的插座上才能工作。Mirko 从房间 $1$ 出发，可以执行以下操作：

如果吸尘器未接通电源，他可以： 在当前所在的房间将其插入插座。 手提吸尘器移动到相邻的房间。穿过走廊需要 $1$ 分钟。

如果吸尘器已接通电源，他可以： 如果他位于插入吸尘器的房间，可以将其从插座上拔下。 移动到相邻的房间，并清扫沿途的走廊。这仅在电缆长度足够时才能执行。也就是说，如果从插入吸尘器的房间到目标房间的距离小于或等于电缆长度。清扫走廊需要 $1$ 分钟。

Mirko 的吸尘器坏了！现在商店里有 $Q$ 个吸尘器，第 $i$ 个吸尘器的电缆长度为 $r_i$ 米。他想知道对于每个吸尘器，如果购买它，清扫所有走廊所需的最短时间是多少。请帮助他确定这些时间！

输入格式

第一行包含自然数 $N$ 和 $Q$，分别表示房间数和吸尘器数量。 接下来的 $N-1$ 行包含自然数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le N, x_i \neq y_i$)，表示房间 $x_i$ 和 $y_i$ 之间存在一条走廊。 最后一行包含 $Q$ 个整数 $r_i$ ($1 \le r_i \le N$)，表示吸尘器的电缆长度。

输出格式

在唯一的一行中输出 $Q$ 个整数，其中第 $i$ 个数字表示使用第 $i$ 个吸尘器清扫所需的最短时间。

子任务

在所有子任务中，$2 \le N \le 3 \cdot 10^5$ 且 $1 \le Q \le 3 \cdot 10^5$。

样例

输入 1

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

输出 1

8 4

说明 1

Mirko 使用电缆长度为 $2$ 米的吸尘器清扫所有走廊的最快方式之一如下： 从房间 $1$ 走到房间 $3$。（$2$ 分钟） 在房间 $3$ 插入吸尘器。 清扫房间 $3$ 与 $4$ 之间以及 $4$ 与 $5$ 之间的走廊。（$2$ 分钟） 回到房间 $3$。（$2$ 分钟） * 清扫房间 $3$ 与 $2$ 之间以及 $2$ 与 $1$ 之间的走廊。（$2$ 分钟）此时所有走廊均已清扫完毕。

输入 2

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

输出 2

24 16

输入 3

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

输出 3

6 12