لاحظ Farmer John أن أبقاره تنتقل كثيرًا بين الحقول القريبة. يريد عشبًا كافيًا بكل حقل للأبقار الأصلية والزائرة من الجوار.

توجد $N$ حقول ($1 \le N \le 100{,}000$)، تربط بعضَها مسارات ثنائية الاتجاه عددها $N-1$. بين أي حقلين $i$ و$j$ طريق وحيد. يعيش في $i$ عدد $C(i)$ أبقار، وقد تنتقل عبر ما لا يزيد عن $K$ مسارات ($1 \le K \le 20$).

يريد إطعام أكبر عدد $M(i)$ قد يصل إلى $i$، أي جميع الأبقار القادرة على الوصول عبر ما لا يزيد عن $K$ مسارات. أوجد كل $M(i)$ من الهيكل وقيم $C(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