Cây là nền tảng cốt lõi của cấu trúc dữ liệu phi tuyến tính và phân cấp. Nó tổ chức thông tin theo mối quan hệ cha-con, được ứng dụng rộng rãi trong lưu trữ dữ liệu, thuật toán tìm kiếm hoặc sắp xếp, cây thư mục, hệ thống tệp tin, và đại diện cho các biểu thức toán học.

Cho một cây gồm ~n~ đỉnh. Các đỉnh được đánh số từ ~1~ đến ~n~. Các đỉnh lần lượt được tô bởi các màu ~c_1, c_2, \dots, c_n~. Với ~2~ đỉnh ~x~ và ~y~ trên cây, ta định nghĩa ~d(x,y)~ là số màu phân biệt trên đường đi đơn duy nhất giữa ~2~ đỉnh ~x~ và ~y~. Với mỗi đỉnh ~u~, hãy tính giá trị ~s_u = d(u,1) + d(u,2) + \dots + d(u,n)~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 4 \cdot 10^5)~ là số đỉnh của cây;

• Dòng thứ hai chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~ ~(1 \le c_i \le n)~ thể hiện màu của các đỉnh;

• Trong ~n-1~ dòng còn lại, mỗi dòng chứa hai số nguyên ~x~ và ~y~ ~(1 \le x, y \le n)~ cho biết trên cây có một cạnh nối hai đỉnh ~x~ và ~y~.

Output

• In ra ~n~ số nguyên ~s_1, s_2, \dots, s_n~. Các số được viết trên một dòng phân cách nhau bởi dấu cách.

Scoring

Sample Input 1

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

Sample Output 1

10 9 11 9 12