Farmer John заметил, что коровы часто переходят между близкими полями. Он хочет посадить на каждом достаточно травы как для местных, так и для приходящих коров.

На ферме $N$ полей ($1 \le N \le 100{,}000$), некоторые соединены двусторонними тропами, всего $N-1$. Между любыми $i$ и $j$ есть единственный путь. На поле $i$ живут $C(i)$ коров, но они могут переходить через не более $K$ троп ($1 \le K \le 20$).

Травы на поле $i$ должно хватить для максимальных $M(i)$ коров, способных оказаться там: всех, кто может дойти по не более $K$ тропам. По структуре фермы и каждому $C(i)$ вычислите все $M(i)$.

Входные данные

• Строка $1$: целые $N$, $K$ через пробел.

• Строки $2\ldots N$: целые $i$, $j$ через пробел ($1 \le i,j \le N$), поля соединены непосредственно.

• Строки $N+1\ldots2N$: строка $N+i$ содержит целое $C(i)$ ($0 \le C(i) \le 1000$).

Выходные данные

• Строки $1\ldots N$: в строке $i$ выведите $M(i)$.

Примеры

Входные данные 1

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

Выходные данные 1

15
21
16
10
8
11

Примечание

Есть $6$ полей, тропы $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, $(3,2)$. На поле $i$ живут $C(i)=i$ коров.

Для поля $1$ в пределах $2$ троп есть $M(1)=15$ коров, и так далее.

Авторы задачи: Neal Wu и Eric Price, 2011