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\ldots 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: Từ tệp văn bản WAW.INP:

• Dòng đầu tiên ghi số nguyên dương \(n\ (1 \leq n \leq 10^{5})\) là số thành viên trong bang;

• Dòng tiếp theo ghi \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\) trong đó \(a_{i}(1 \leq a_{i} \leq 10^{9})\) là loại lính của thành viên thứ \(i\ (i = 1\ldots n)\);

• \(n - 1\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(x,\ y\ (1 \leq x,y \leq 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ả: Đưa ra tệp văn bản WAW.OUT gồm \(n\) số nguyên, trong đó số thứ \(i\ (i = 1\ldots n)\) là sức mạnh của thành viên thứ \(i\).

Ví dụ:

Giải thích: Trong ví dụ 2:

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 chính là loại lí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 thành viên 3 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 thành viên 1 là loại lính 2 thì loại lính 2 và 3 xuất hiện nhiều nhất (cùng số lần là 3) nên sức mạnh của thành viên 1 là \(2 + 3 = 5\).

Ràng buộc:

+ Có 30% số test tương ứng 30% số điểm có \(1 \leq n,\ a_{i} \leq 200;\ \)

+ Có 30% số test khác tương ứng 30% số điểm có \(200 < n \leq 2000\);

+ Có 40% số test còn lại tương ứng 40% số điểm có \(2000 \leq n \leq 10^{5}\).