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$ יש $M(1)=15$ פרות במרחק עד $2$ שבילים, וכן הלאה.

מחברי הבעיה: Neal Wu ו-Eric Price, 2011