Vào kỳ nghỉ Chủ Nhật, _minhduc đã cùng các bạn đi dạo chơi quanh phố. Khi đi ngang qua khu vui chơi, thì bất chợt có một tờ giấy bay qua, và bay đúng vào mặt của _minhduc. Tờ giấy đó là nội dung của trò chơi có thưởng của tay code số một server LQDOJ, kèm theo đó là một bài toán như sau:

Cho \(N\) địa điểm và \(N – 1\) con đường hai chiều nối trực tiếp giữa hai địa điểm, đảm bảo rằng giữa hai địa điểm bất kỳ chỉ có duy nhất một đường đi.

Mỗi địa điểm \(i\) sẽ có một biểu tượng mang con số là \(A_i\). Ta định nghĩa \(F_{u,v}\) là số các biểu tượng khác nhau của các địa điểm trên đường đi từ \(u\) tới \(v\). Và \(S_u\) là tổng tất cả các \(F_{u,v}\) với mọi \(v \in [1;N]\).

Yêu cầu của trò chơi là đưa ra tất cả kết quả \(S_u\) với \(u \in [1;N]\). Giải được trò chơi này sẽ được một vé đi xem phim "Đất rừng phương Nam" miễn phí.

Vì trước giờ là thành viên trong đội tuyển quốc gia, với lại đây là trò chơi tay code số một server LQDOJ mà lâu nay ngưỡng mộ, nên _minhduc muốn ra tay với bài toán trong trò chơi này để giành lấy vé xem phim ấy. Nhưng khổ nỗi là _minhduc đã quên mang Macbook M2 Pro của anh ta đi, với lại không muốn chịu thua, nên các bạn hãy giúp _minhduc có đáp án nhé.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\). \((1 \le N \le 10^5)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1,A_2,...,A_N\) \((1 \le A_i \le 10^5)\)
• \(N-1\) dòng còn lại, mỗi dòng mỗi dòng chứa cặp số nguyên dương \(u,v\) thể hiện có con đường nối trực tiếp giữa hai địa điểm \(u,v\) \((1 \le u,v \le N,u \neq v)\).

Output

• Gồm \(N\) dòng, dòng thứ \(u\) chứa số nguyên dương duy nhất \(S_u\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 200\).
• Subtask \(2\) (\(30\%\) số điểm): Có \(N \le 2000\).
• Subtask \(3\) (\(10\%\) số điểm): Có các địa điểm nối với nhau theo một đường thẳng.
• Subtask \(4\) (\(10\%\) số điểm): Có các số \(A_i\) đôi một phân biệt.
• Subtask \(5\) (\(10\%\) số điểm): Có \(A_i \le 10\).
• Subtask \(6\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

11
8
8
11
11