Farmer John nota che le mucche passano tra campi vicini. Vuole piantare erba sufficiente per quelle locali e quelle in visita.

La fattoria ha $N$ campi ($1 \le N \le 100{,}000$), alcuni collegati da sentieri bidirezionali, $N-1$ in totale. Tra qualunque $i$, $j$ il percorso è unico. Il campo $i$ ospita $C(i)$ mucche, che a volte attraversano fino a $K$ sentieri ($1 \le K \le 20$).

Vuole nutrire il massimo $M(i)$ che può arrivare a $i$: tutte quelle che raggiungono il campo su al massimo $K$ sentieri. Con struttura e ogni $C(i)$ calcola tutti gli $M(i)$.

Input

• Riga $1$: interi $N$, $K$ separati da uno spazio.

• Righe $2\ldots N$: interi $i$, $j$ separati da uno spazio ($1 \le i,j \le N$), campi collegati direttamente.

• Righe $N+1\ldots2N$: la riga $N+i$ dà intero $C(i)$ ($0 \le C(i) \le 1000$).

Output

• Righe $1\ldots N$: la riga $i$ dà $M(i)$.

Esempi

Input 1

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

Output 1

15
21
16
10
8
11

Spiegazione

Ci sono $6$ campi, sentieri $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, $(3,2)$. Il campo $i$ ha $C(i)=i$ mucche.

In $1$ ci sono $M(1)=15$ mucche entro $2$ sentieri, ecc.

Autori del problema: Neal Wu ed Eric Price, 2011