Thành có một cây gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~. Mỗi đỉnh ~i~ có trọng số là ~a_i~.

Thành muốn tìm hiểu các vùng liên thông trong cây. Một vùng liên thông được định nghĩa là một tập các đỉnh sao cho giữa hai đỉnh bất kỳ trong tập này luôn tồn tại một đường đi chỉ gồm các đỉnh trong tập đó.

Với mỗi số nguyên ~k~ từ ~1~ đến ~n~, hãy xác định tổng trọng số lớn nhất của một vùng liên thông gồm đúng ~k~ đỉnh.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 5000~) — số lượng đỉnh của cây.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \leq 10^4~) — trọng số của các đỉnh.

Mỗi dòng trong ~n-1~ dòng tiếp theo chứa hai số nguyên ~u~ và ~v~ (~1 \leq u, v \leq n~) — biểu diễn một cạnh nối đỉnh ~u~ và ~v~.

Output

In ra ~n~ dòng, dòng thứ ~k~ chứa một số nguyên là tổng trọng số lớn nhất của một vùng liên thông gồm đúng ~k~ đỉnh.

Sample Input 1

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

Sample Output 1

5
8
12
13
15

Giải thích

Với ~k = 1~: chọn đỉnh có trọng số lớn nhất là đỉnh 5 → ~5~

Với ~k = 2~: chọn đỉnh 5 và 3 → ~5 + 3 = 8~

Với ~k = 3~: chọn 3-4-5 → ~3 + 4 + 5 = 12~

Với ~k = 4~: chọn 1-3-4-5 → ~1 + 3 + 4 + 5 = 13~

Với ~k = 5~: toàn bộ cây → ~1 + 2 + 3 + 4 + 5 = 15~