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 年