Trong khu rừng cổ, PhuocThien phát hiện một cổ thụ thần có bộ rễ nối thành một cây gồm \(n\) đỉnh. Mỗi đỉnh mang một chỉ số sinh mệnh. Khi cổ thụ hấp thụ ánh sáng, năng lượng không lan đều mà chỉ truyền theo những nhánh đủ “điều kiện cộng hưởng”.

DatthicTech và conghieupt2555 biết được bí mật ấy nên đã đặt lên cây một chuỗi nghi thức.
Mỗi nghi thức chọn một đỉnh \(u\) làm gốc, rồi yêu cầu xét toàn bộ các đỉnh trong cây con của \(u\) theo cây đã được cố định gốc tại đỉnh \(1\).

Với một nghi thức tại đỉnh \(u\), PhuocThien có thể chọn đúng \(k\) đỉnh bất kỳ trong cây con của \(u\), nhưng các đỉnh được chọn phải tạo thành một tập liên thông. Giá trị của một tập được tính bằng tổng sinh mệnh của các đỉnh trong tập đó.

Nhiệm vụ của bạn là với mỗi đỉnh \(u\), hãy tìm giá trị lớn nhất của một tập gồm đúng \(k\) đỉnh, liên thông và nằm hoàn toàn trong cây con của đỉnh \(u\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n, k\) \((1 \le n \le 5000,\ 1 \le k \le min(n, 200))\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((-10^9 \le a_i \le 10^9)\) — chỉ số sinh mệnh của các đỉnh.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \le u, v \le n)\), mô tả một cạnh của cây.

Cây được gốc hóa tại đỉnh \(1\).

Output

In ra \(n\) dòng.
Dòng thứ \(u\) chứa một số nguyên là giá trị lớn nhất của một tập gồm đúng \(k\) đỉnh, liên thông và nằm trong cây con của đỉnh \(u\).
Nếu không tồn tại tập như vậy, in ra -1.

Example

5 3
3 1 -2 4 2
1 2
1 3
2 4
2 5

8
7
-1
-1
-1

4 2
-5 10 -1 7
1 2
2 3
3 4

9
9
6
-1

Scoring

• Subtask \(1\) (\(25\%\)): \(n \le 200\), \(k \le 20\).
• Subtask \(2\) (\(35\%\)): Cây là đường thẳng.
• Subtask \(3\) (\(40\%\)): Không có ràng buộc thêm.