Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~n-1~ cạnh thỏa mãn với mọi cặp đỉnh ~u, v~ của đồ thị tồn tại ít nhất ~1~ đườ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, \dots, 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ử (các 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, \dots, v_m~ là ~a_{v_1}+a_{v_2}+\dots+a_{v_m}~. Tìm độ đẹp lớn nhất của một thành phần liên thông gồm ~k~ đỉnh trên đồ thị đã cho ở trên với mọi ~k~ từ ~1~ đến ~n~.

Input

Dòng đầu tiên gồm ~1~ số nguyên dương ~n~ ~(1 \le n \le 5000)~.

Dòng thứ ~2~ gồm ~n~ số nguyên dương lần lượt là ~a_1, \dots, a_n~, các số tách nhau bởi một dấu cách (~-10^4 \le a_i \le 10^4~ với mọi ~i~ từ ~1~ đến ~n~).

~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm ~2~ số nguyên dương ~u_i, v_i~ ~(1 \le u_i, v_i \le n)~ biểu thị cho cạnh thứ ~i~ của đồ thị.

Output

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

Scoring

Sample Input 1

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

Sample Output 1

10 19 25 29 34 35 35 35

Sample Input 2

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

Sample Output 2

10 10 13 19 23 25 26

Sample Input 3

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

Sample Output 3

7 8 11 12 16 19