Farmer John notou que vacas se movem entre campos próximos. Quer plantar grama suficiente para as vacas locais e visitantes em cada campo.

São $N$ campos ($1 \le N \le 100{,}000$), alguns ligados por trilhas bidirecionais, $N-1$ ao todo. Entre quaisquer $i$, $j$ há caminho único. O campo $i$ abriga $C(i)$ vacas, que às vezes cruzam até $K$ trilhas ($1 \le K \le 20$).

Deve alimentar o máximo $M(i)$ que pode chegar a $i$: todas as vacas capazes de alcançar o campo por no máximo $K$ trilhas. Com a estrutura e cada $C(i)$ calcule todos os $M(i)$.

Entrada

• Linha $1$: inteiros $N$, $K$ separados por um espaço.

• Linhas $2\ldots N$: inteiros $i$, $j$ separados por um espaço ($1 \le i,j \le N$), campos diretamente ligados.

• Linhas $N+1\ldots2N$: a linha $N+i$ contém inteiro $C(i)$ ($0 \le C(i) \le 1000$).

Saída

• Linhas $1\ldots N$: a linha $i$ contém $M(i)$.

Exemplos

Entrada 1

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

Saída 1

15
21
16
10
8
11

Explicação

Há $6$ campos, trilhas $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, $(3,2)$. O campo $i$ tem $C(i)=i$ vacas.

Em $1$ há $M(1)=15$ vacas a distância de até $2$ trilhas, etc.

Autores do problema: Neal Wu e Eric Price, 2011