Bạn được cho một cây có gốc gồm n nút. Các nút được đánh số 1,2,~\ldots~,n và nút 1 là nút gốc. Mỗi nút có một màu.

Nhiệm vụ của bạn là xác định cho mỗi nút số lượng màu riêng biệt trong cây con của nút đó.

Input

Dòng đầu tiên chứa số nguyên n: số nút. Các nút được đánh số 1,2,~\ldots~,n.

Dòng tiếp theo gồm n số nguyên ~c_1,c_2,...,c_n~: màu của mỗi nút.

Khi đó có n-1 dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên u và v: có một cạnh giữa các nút u và v.

Output

In ra n số nguyên: với mỗi nút 1,2,~\ldots~,n là số lượng màu phân biệt.

Hạn chế

~1 \le n \le 2 \cdot 10^5~

~1 \le u, v \le n~

~1 \le c_i \le 10^9~

Examples

Input

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

Output

3 1 2 1 1