Trò chơi War and war (WAW) vừa mới xuất hiện trên thị trường nhưng đã thu hút được rất nhiều người chơi trên thế giới bởi có nhiều chức năng thú vị mà các trò chơi khác không có.

Tèo là một người chơi tham gia trò chơi WAW ngay từ đầu. Tèo đang ở trong một bang có ~ n ~ thành viên. Tèo có số thứ tự là 1, các thành viên khác được đánh số thứ tự từ 2 đến ~ n ~, thành viên thứ ~ i ~ ~ (i = 1…n) ~ có loại lính ~ a_i ~. Trong bang một thành viên có thể quản lý một số thành viên khác. Tèo là thủ lĩnh nên Tèo quản lý tất cả các thành viên trong bang. Với hai thành viên ~ x ~ và ~ y ~, bang quy định ~ x ~ là người quản lý của ~ y ~, ~ x ~ cũng quản lý tất cả thành viên mà ~ y ~ quản lý. Sức mạnh của một thành viên ~ x ~ được xác định là tổng của những loại lính xuất hiện nhiều nhất trong những thành viên mà ~ x ~ quản lý (bao gồm cả loại lính của ~ x ~).

Yêu cầu: Hãy cho biết sức mạnh của mỗi thành viên trong bang.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ n ~ ~ (1 ≤ n ≤ 10^5) ~ là số thành viên trong bang;
• Dòng tiếp theo ghi ~ n ~ số nguyên ~ a_1, a_2, …, a_n ~ trong đó ~ a_i ~ ~ (1 ≤ a_i ≤ 10^9) ~ là loại lính của thành viên thứ ~ i ~ ~ ( i = 1…n) ~;
• ~ n-1 ~ dòng tiếp theo, mỗi dòng ghi hai số nguyên ~ x, y ~ ~ (1 ≤ x, y ≤ n) ~ cho biết ~ x ~ là người quản lý của ~ y ~.

Dữ liệu luôn đảm bảo nếu ~x~ quản lý ~y~ thì ~y~ không quản lý ~x~.

Kết quả

Gồm ~ n ~ số nguyên, trong đó số thứ ~ i ~ ~ ( i = 1…n) ~ là sức mạnh của thành viên thứ ~ i ~.

Ràng buộc

• Có 30% số test có ~ 1 ≤ n, a_i ≤ 200 ~;
• Có 30% số test có ~ 200 ≤ n ≤ 2000 ~;
• Có 40% số test có ~ 2000 ≤ n ≤ 10^5 ~.

Ví dụ:

Input 1

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

Output 1

1 3 3 4 1 1 1 

Input 2

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

Output 2

5 3 2 3 3 2