在 IOI 国有 $N$ 座城镇，编号为 $1$ 到 $N$。此外，IOI 国还有 $N - 1$ 条道路，编号为 $1$ 到 $N - 1$。第 $j$ 条道路 ($1 \le j \le N - 1$) 连接城镇 $U_j$ 和城镇 $V_j$，且双向通行。通过若干条道路，可以从任意城镇到达其他任意城镇。

现在 IOI 国将举办一场集邮拉力赛。每个城镇都将设置一个邮戳站。城镇 $i$ ($1 \le i \le N$) 的邮戳站将在时间 $T_i$ 安装。

JOI-kun 决定参加这场集邮拉力赛。在时间 $0$，JOI-kun 从其中一个城镇出发。此外，JOI-kun 在时间 $0$ 时拥有体力 $D$。

当 JOI-kun 在时间 $t$ 位于城镇 $i$ 时，他会执行以下操作：

1. 首先，如果当前城镇已经安装了邮戳站，他会盖章。也就是说，如果 $T_i \le t$，他就会盖章。
2. 接下来，他可以选择结束集邮拉力赛，或者移动到另一个城镇。但是，只有当存在一个与城镇 $i$ 相连且他尚未访问过的相邻城镇，且他当前的体力至少为 $1$ 时，他才能选择移动到另一个城镇。
3. 如果 JOI-kun 选择移动到另一个城镇，他会在与城镇 $i$ 相连的城镇中选择一个未访问过的城镇 $j$，并移动到那里。他的体力减少 $1$，并在时间 $t + 1$ 到达城镇 $j$。
4. 如果 JOI-kun 选择结束集邮拉力赛，若他在此之前至少盖过一次章，则拉力赛成功，他可以在那里领取一份礼物。否则，拉力赛失败。

假设除城镇间的旅行时间外，所有时间均可忽略不计。注意，JOI-kun 不能停留在同一个城镇。

你是活动组织者。如果 JOI-kun 的集邮拉力赛成功，你需要准备相应的礼物。然而，礼物的数量有限，因此你希望准备礼物的城镇数量尽可能少。不幸的是，你不知道 JOI-kun 会从哪个城镇出发。因此，对于每个 $s$ ($1 \le s \le N$)，你想要找出当 JOI-kun 从城镇 $s$ 出发时，必须准备礼物的城镇数量。换句话说，你需要计算满足以下条件的 $g$ ($1 \le g \le N$) 的数量：当 JOI-kun 在城镇 $g$ 结束时，集邮拉力赛有可能成功。

给定有关 IOI 国城镇和道路的信息、JOI-kun 的体力以及邮戳站的安装时间，编写一个程序，计算对于每个城镇，当 JOI-kun 从该城镇出发时，必须准备礼物的城镇数量。

输入格式

从标准输入读取以下数据：

$N \ D$ $T_1 \ T_2 \ \dots \ T_N$ $U_1 \ V_1$ $U_2 \ V_2$ $\vdots$ $U_{N-1} \ V_{N-1}$

输出格式

向标准输出写入 $N$ 行。第 $s$ 行 ($1 \le s \le N$) 应包含当 JOI-kun 从城镇 $s$ 出发时，必须准备礼物的城镇数量。

数据范围

• $2 \le N \le 400\,000$。
• $0 \le D \le N - 1$。
• $0 \le T_i \le N$ ($1 \le i \le N$)。
• $1 \le U_j < V_j \le N$ ($1 \le j \le N - 1$)。
• 可以通过若干条道路从任意城镇到达其他任意城镇。
• 给定值均为整数。

子任务

1. (3 分) $D \le 1$。
2. (7 分) $N \le 3\,000$, $(U_j, V_j) = (j, j + 1)$ ($1 \le j \le N - 1$)。
3. (10 分) $N \le 3\,000$。
4. (11 分) $(U_j, V_j) = (j, j + 1)$ ($1 \le j \le N - 1$)。
5. (41 分) $D = N - 1, N \le 150\,000$。
6. (28 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

2
3
4
2
2

样例输入 2

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

样例输出 2

2
1
2
0
1

样例输入 3

7 6
2 3 0 4 1 3 4
1 2
2 3
2 4
1 5
1 6
6 7

样例输出 3

2
2
7
5
1
2
5