Farmer John zauważył, że krowy przechodzą między pobliskimi polami. Chce posadzić dość trawy na każdym dla miejscowych i odwiedzających krów.

Jest $N$ pól ($1 \le N \le 100{,}000$), niektóre łączą dwukierunkowe ścieżki, łącznie $N-1$. Między dowolnymi $i$, $j$ jest jedyna droga. Na $i$ mieszka $C(i)$ krów, które mogą przejść najwyżej $K$ ścieżek ($1 \le K \le 20$).

Pole $i$ powinno wyżywić maksymalne $M(i)$ krów mogących tam dotrzeć: wszystkie docierające po najwyżej $K$ ścieżkach. Z układu i każdego $C(i)$ oblicz wszystkie $M(i)$.

Wejście

• Wiersz $1$: całkowite $N$, $K$ rozdzielone spacją.

• Wiersze $2\ldots N$: całkowite $i$, $j$ ze spacją ($1 \le i,j \le N$), pola bezpośrednio połączone.

• Wiersze $N+1\ldots2N$: wiersz $N+i$ zawiera całkowite $C(i)$ ($0 \le C(i) \le 1000$).

Wyjście

• Wiersze $1\ldots N$: wiersz $i$ zawiera $M(i)$.

Przykład

Wejście 1

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

Wyjście 1

15
21
16
10
8
11

Uwagi

Jest $6$ pól i ścieżki $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, $(3,2)$. Pole $i$ ma $C(i)=i$ krów.

Pole $1$ ma $M(1)=15$ krów w odległości najwyżej $2$ ścieżek itd.

Autorzy zadania: Neal Wu i Eric Price, 2011