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