花之国由 $n$ 个城市组成，第 $i$ 个城市种植了 $a_i$ 朵花。共有 $n-1$ 条道路，其中第 $i$ 条道路连接城市 $u_i$ 和 $v_i$。保证任意两个城市之间都有路径相连。

现在，花之国想要举办一场花卉展览。为此，你需要首先选择一个城市 $z$ 作为展览馆所在地，然后选择恰好 $k$ 个城市 $x_1, x_2, \dots, x_k$，并将这些城市的花运送到城市 $z$。

为了避免沿途城市居民的不满，组织者规定：如果选择了城市 $x$，那么从 $x$ 到 $z$ 路径上的所有城市也必须被选中。特别地，这意味着城市 $z$ 本身必须被选中。

对于每个 $z = 1, 2, \dots, n$，求出若选择城市 $z$ 作为展览馆所在地，所能运送的花朵数量的最大值。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 40\,000, 1 \le k \le \min(n, 3000)$)。 下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5 \cdot 10^5$)。 接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n, x \neq y$)，表示顶点 $x$ 和 $y$ 之间有一条边。保证给定的图是一棵树。

输出格式

输出一行，包含 $n$ 个整数 $f_1, f_2, \dots, f_n$，其中 $f_i$ 表示 $z = i$ 时的答案。

样例

输入 1

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

输出 1

20 20 17 17 20

输入 2

7 4
1 3 2 1 7 12 17
4 6
1 4
5 1
2 5
7 6
3 2

输出 2

31 13 13 31 21 31 31