Farmer John ha visto que las vacas se mueven entre campos cercanos. Quiere plantar suficiente hierba en cada uno para las vacas locales y visitantes.

La granja tiene $N$ campos ($1 \le N \le 100{,}000$), algunos unidos por senderos bidireccionales, $N-1$ en total. Entre cualesquiera $i$, $j$ hay un único camino. En $i$ viven $C(i)$ vacas, que a veces cruzan hasta $K$ senderos ($1 \le K \le 20$).

Debe alimentar el máximo $M(i)$ que podría llegar a $i$: todas las vacas que alcanzan el campo cruzando como máximo $K$ senderos. Con la estructura y cada $C(i)$ calcula todos los $M(i)$.

Entrada

• Línea $1$: enteros $N$, $K$ separados por un espacio.

• Líneas $2\ldots N$: enteros $i$, $j$ separados por un espacio ($1 \le i,j \le N$), campos directamente unidos.

• Líneas $N+1\ldots2N$: la línea $N+i$ contiene entero $C(i)$ ($0 \le C(i) \le 1000$).

Salida

• Líneas $1\ldots N$: la línea $i$ contiene $M(i)$.

Ejemplos

Entrada 1

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

Salida 1

15
21
16
10
8
11

Nota

Hay $6$ campos, senderos $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, $(3,2)$. El campo $i$ tiene $C(i)=i$ vacas.

En $1$ hay $M(1)=15$ vacas a distancia de como máximo $2$ senderos, etc.

Autores del problema: Neal Wu y Eric Price, 2011