题目描述

农夫约翰发现他的奶牛经常在相邻的草地之间走动。考虑到这一点，他想在每块草地上种植足够多的草，不仅要满足最初在那里的奶牛，还要照顾从附近走过来的奶牛。

约翰的农场共有 $N$（$1 \leq N \leq 100000$）块草地，其中 $N-1$ 条双向小径将某些草地两两相连。约翰将农场设计成：任意两块草地 $i$ 和 $j$ 之间恰好有一条由小径组成的唯一路径。

第 $i$ 块草地上有 $C_i$（$0 \leq C_i \leq 1000$）只奶牛，但奶牛有时会走到其他草地上，最多跨越 $K$（$1 \leq K \leq 20$）条小径。

约翰想在每块草地 $i$ 上种植足够多的草，以喂饱可能到达该草地的最大奶牛数 $M_i$——即所有通过至多 $K$ 条小径即可到达草地 $i$ 的奶牛总数。请帮约翰计算每块草地 $i$ 的 $M_i$。

输入格式

第 $1$ 行：两个空格分隔的整数 $N$ 和 $K$。

第 $2$ 到 $N$ 行：每行两个空格分隔的整数 $i$ 和 $j$（$1 \leq i,j \leq N$），表示草地 $i$ 和 $j$ 之间有一条小径直接相连。

第 $N+1$ 到 $2N$ 行：第 $N+i$ 行包含一个整数 $C_i$（$0 \leq C_i \leq 1000$）。

输出格式

共 $N$ 行，第 $i$ 行输出 $M_i$ 的值。

样例

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

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$ 只奶牛，以此类推。