Nam đang ở trong một đội có \(n\) thành viên. Nam 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 là \(a_i\).

Trong đội, một thành viên có thể quản lý một số thành viên khác. Nam là lãnh đạo nên Nam quản lý tất cả các thành viên trong đội. Với hai thành viên \(x\) và \(y\), trò chơi quy định nếu \(x\) là người quản lý của \(y\) thì \(x\) cũng quản lý tất cả cá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 đội.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương \(n\) \((1 \le n \le 10^5)\) là số thành viên trong đội.
• Dòng thứ hai ghi \(n\) số nguyên \(a_1,a_2...a_n\) trong đó \(a_i\) \((1 \le a_i \le 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 \le x, y \le 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\).

Dữ liệu ra

• \(n\) số nguyên trên một dòng, mỗi số cách nhau \(1\) khoảng trắng, trong đó số thứ \(i\) \((i = 1...n)\) là sức mạnh của thành viên thứ \(i\).

Input 1

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

Output 1

5 3 2 3 3 2

Input 2

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

Output 2

1 3 3 4 1 1 1

Giải thích:

• Trong ví dụ \(1\):
• Các thành viên \(2, 4, 5, 6\) không quản lý thành viên khác nên sức mạnh của những thành viên này cũng chính là loại lính của mình.
• Thành viên \(3\) quản lý thành viên \(5, 6\) và tính thêm loại lính của nó thì loại lính \(2\) xuất hiện nhiều nhất nên sức mạnh của thành viên \(3\) là \(2\).
• Thành viên \(1\) quản lý tất cả các thành viên còn lại và tính thêm loại lính của nó thì loại lính \(2\) và \(3\) xuất hiện nhiều nhất (số lần là \(3\)) nên sức mạnh của thành viên \(1\) là \(2 + 3 = 5\).