Farmer John bemerkt, dass Kühe oft zwischen nahen Feldern wechseln. Er möchte genug Gras für die anfangs dort lebenden und die besuchenden Kühe pflanzen.

Es gibt $N$ Felder ($1 \le N \le 100{,}000$), einige durch beidseitig nutzbare Pfade verbunden, insgesamt $N-1$. Zwischen allen $i$, $j$ gibt es einen eindeutigen Weg. Auf $i$ leben $C(i)$ Kühe, die manchmal über höchstens $K$ Pfade ($1 \le K \le 20$) in ein anderes Feld wechseln.

Feld $i$ soll die maximal möglichen $M(i)$ Kühe ernähren: alle, die es über höchstens $K$ Pfade erreichen können. Berechne aus Struktur und allen $C(i)$ jedes $M(i)$.

Eingabe

• Zeile $1$: ganze Zahlen $N$, $K$, durch ein Leerzeichen getrennt.

• Zeilen $2\ldots N$: ganze Zahlen $i$, $j$ mit Leerzeichen ($1 \le i,j \le N$), direkt verbundene Felder.

• Zeilen $N+1\ldots2N$: Zeile $N+i$ enthält ganzzahliges $C(i)$ ($0 \le C(i) \le 1000$).

Ausgabe

• Zeilen $1\ldots N$: Zeile $i$ enthält $M(i)$.

Beispiele

Eingabe 1

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

Ausgabe 1

15
21
16
10
8
11

Hinweis

Es gibt $6$ Felder und Pfade $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, $(3,2)$. Feld $i$ hat $C(i)=i$ Kühe.

Feld $1$ hat $M(1)=15$ Kühe in Entfernung von höchstens $2$ Pfaden, usw.

Autoren der Aufgabe: Neal Wu und Eric Price, 2011