Cho một cây gồm ~N~ đỉnh, mỗi đỉnh có một màu khác nhau. Gọi ~d\left(u, v\right)~ là số màu phân biệt trên đường đi từ đỉnh ~u~ tới đỉnh ~v~. Đặt ~sum(u) = d(u, 1) + d(u, 2) + … + d(u, N)~. Hãy tính ~sum(u)~ với mọi đỉnh ~u~ bất kì.

Input

• Dòng đầu tiên chứa số nguyên ~N~.
• Dòng thứ hai chứa ~N~ số nguyên ~c_1,c_2,…,c_N~ lần lượt là màu của các đỉnh.
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ mô tả một cạnh của cây nối giữa hai đỉnh ~u~ và ~v~. Dữ liệu vào đảm bảo đồ thị có dạng là cây.

Giới hạn:

• ~1≤c_i≤10^5~ với mọi ~1≤i≤N~
• Subtask #~1~: ~10\%~ số điểm: ~N\le300~
• Subtask #~2~: ~18\%~ số điểm: ~N\le5000~
• Subtask #~3~: ~12\%~ số điểm: Mọi đỉnh có cùng màu
• Subtask #~4~: ~24\%~ số điểm: Không tồn tại hai đỉnh cùng màu
• Subtask #~5~: ~36\%~ số điểm: Không có ràng buộc gì thêm.

Output

• Gồm ~N~ dòng, dòng thứ ~i~ chứa số nguyên ~sum(i)~.

Sample

Input #1

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

Output #1

10
9
11
9
12

Hint

Problem source: PreVNOI Ⅶ Lần 2 (ONLINE 2017)