Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(n-1\) cạnh, sao cho với mọi cặp đỉnh \(u\), \(v\), tồn tại ít nhất một đường đi từ \(u\) đến \(v\). Các đỉnh được đánh số từ \(1\) đến \(n\).

Định nghĩa một thành phần liên thông gồm \(m\) đỉnh \(v_1, ..., v_m\) là một tập hợp các đỉnh thỏa mãn: với mọi cặp \((i, j)\), tồn tại ít nhất một đường đi từ \(v_i\) đến \(v_j\) mà không đi qua bất kỳ đỉnh nào không thuộc tập \(v\).

Cho một dãy \(a\) có \(n\) phần tử (đánh số từ \(1\) đến \(n\)). Gọi độ đẹp của một thành phần liên thông gồm \(m\) đỉnh \(v_1, ..., v_m\) là:

\[a_{v_1} + a_{v_2} + ... + a_{v_m}\]

Yêu cầu: Tìm độ đẹp lớn nhất của một thành phần liên thông gồm \(k\) đỉnh với mọi \(k\) từ \(1\) đến \(n\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 5000\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, ..., a_n\) (\(-10^4 \le a_i \le 10^4\)).
• \(n - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u_i\), \(v_i\) (\(1 \le u_i, v_i \le n\)) biểu diễn một cạnh của đồ thị.

Output

• In ra \(n\) số \(d_1, ..., d_n\) — trong đó \(d_k\) là độ đẹp lớn nhất của thành phần liên thông gồm \(k\) đỉnh. Các số in trên một dòng, cách nhau bởi dấu cách.

Examples

Input

8
6 9 1 4 10 0 5 0
1 2
3 1
1 4
2 5
2 6
4 7
7 8

Output

10 19 25 29 34 35 35 35

Input

7
3 0 6 2 10 4 1
2 1
3 1
4 2
5 2
6 3
7 3

Output

10 10 13 19 23 25 26

Input

6
1 7 7 0 1 3
1 4
4 2
1 5
5 6
5 3

Output

7 8 11 12 16 19

Scoring

• Subtask 1 (10%): \(n \le 18\)
• Subtask 2 (20%): \(n \le 300\), đỉnh \(1\) có tối đa 2 đỉnh kề, và mỗi đỉnh tối đa 3 đỉnh kề
• Subtask 3 (40%): \(n \le 300\)
• Subtask 4 (20%): \(n = 2^k - 1\) với \(u_i = i+1\), \(v_i = ⌊(i+1)/2⌋\)
• Subtask 5 (10%): Không có điều kiện gì thêm