该城市包含 $n$ 个地点，编号从 $1$ 到 $n$，由 $n-1$ 条双向道路连接。每条道路的长度为 $1$。也就是说，该城市在图论中是一棵树。

Nikuniku 在机械工厂工作，需要在城市中选择一个地点 $t$ 来建造一个新的车间。

地点 $i$ 有 $a_i$ 名员工居住。

在选择目标地点后，Nikuniku 将设计至多 $k$ 条班车路线，以帮助员工从家通勤到工厂。第 $i$ 条路线是地点 $s_i$ 和 $t$ 之间的一条简单路径（包含 $s_i$ 和 $t$）。

每位员工会步行到至少有一条路线经过的最近地点，然后乘车。班车的容量足够大，因此无需担心。一位员工的步行距离是他居住地点到上车地点之间的最短路径长度。

Nikuniku 想知道，如果她选择地点 $t$ 建造车间并设计合适的路线，对于每个地点 $t$ ($1 \le t \le n$)，所有员工的最小总步行距离是多少。

但 Nikuniku 因为请了太多带薪假刚被解雇，所以请你利用你的编程技能来帮助她。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 2 \cdot 10^5$) 和 $k$ ($1 \le k \le n$)，分别表示地点数量和班车路线数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)，表示居住在每个地点的员工人数。

接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n, x \neq y$)，表示地点 $x$ 和 $y$ 之间有一条道路。

保证这些道路构成一棵树。

输出格式

输出 $n$ 行。第 $i$ 行输出一个整数，表示在地点 $i$ 建造车间时的最小总步行距离。

样例

输入 1

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

输出 1

2
0
0
3
0

输入 2

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

输出 2

3
3
1
2
3
1
1
1