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$ 本の小道で到達できる牛に足りる草を植えたいのです。構造と各 $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 年