题目描述

小A的牧场里有里有多块草地，每块草地上有若干只羊，他的羊群经常在草地之间移动。为了确保每块草地的羊都有足够的草，小A决定不仅要考虑每块草地本身的养羊的数量，还要计算周围草地可能会到来的羊的数量。

牧场包含 $N$ 块草地，这些草地之间通过双向小路相连，总共有 $N - 1$ 条小路，连接了所有的草地。

第 $i$ 块草地上有 $A_i$ 只羊，小羊可能通过跨越最多 $C$ 条小路去往其他草地。

小A希望为每块草地计算出能到达该草地的最多羊的数量，但他的牧场实在太大了，他不得不求助于聪明的你。

请你编程帮小A计算出，对于每块草地，最多能到达该草地的羊的数量。

输入格式

第 $1$ 行读入 $2$ 个整数，$N$ 和 $C$。

接下来 $N - 1$ 行，每行两个空格分隔的整数 $U_i, V_i$，表示编号为 $U_i$ 和编号为 $V_i$ 的草地之间有一条双向的小路。

接下来 $N$ 行，每行有一个整数 $A_i$，表示编号为 $i$ 的草地上羊的数量。

输出格式

输出 $N$ 行，第 $i$ 行输出的是，对于编号为 $i$ 的草地，最多能到达该草地的羊的数量。

样例

输入

6 2
1 2
1 3
3 4
3 5
5 6
10
20
30
40
50
60

输出

150
60
210
130
190
140

数据范围

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$1 \le C \le 20$，$1 \le U_i, V_i \le N$，$0 \le A_i \le 1000$。