Farmer John 发现牛经常在附近的田地间移动。因此他希望每块田都种足够的草，既供原本的牛，也供附近来访的牛。

农场有 $N$ 块田（$1 \le N \le 100{,}000$），某些田间有双向小径，共 $N-1$ 条。任意两块田 $i$、$j$ 间恰有一条由小径组成的路径。田 $i$ 原有 $C(i)$ 头牛，但牛有时经过至多 $K$ 条小径（$1 \le K \le 20$）到其他田。

他希望田 $i$ 的草足够供可能到达的最大牛数 $M(i)$，即经过至多 $K$ 条小径能到达田 $i$ 的所有牛。给定农场结构和每块田的 $C(i)$，求每块田的 $M(i)$。

输入格式

• 第 $1$ 行：以空格分隔的整数 $N$、$K$。

• 第 $2\ldots N$ 行：每行以空格分隔的整数 $i$、$j$（$1 \le i,j \le N$），表示有小径直接连接。

• 第 $N+1\ldots2N$ 行：第 $N+i$ 行包含整数 $C(i)$（$0 \le C(i) \le 1000$）。

输出格式

• 第 $1\ldots N$ 行：第 $i$ 行输出 $M(i)$。

样例

输入格式 1

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

输出格式 1

15
21
16
10
8
11

说明

有 $6$ 块田，小径连接 $(5,1)$、$(3,6)$、$(2,4)$、$(2,1)$、$(3,2)$。田 $i$ 有 $C(i)=i$ 头牛。

田 $1$ 在至多 $2$ 条小径距离内有 $M(1)=15$ 头牛，其他类推。

题目作者：Neal Wu 和 Eric Price，2011 年