Cho một cây có gốc bao gồm \(n\) nút. Các nút được đánh số \(1, 2, \ldots, n\) và nút \(1\) là gốc của cây. Mỗi nút có một màu.

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

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 2 \cdot 10^5)\) - số lượng nút. Các nút được đánh số \(1, 2, \ldots, n\)
• Dòng tiếp theo bao gồm \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) \((1 \leq c_i \leq 10^9)\) - màu sắc của mỗi nút
• Sau đó, có \(n-1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) - có một cạnh nối hai nút \(a\) và \(b\)

Output

• \(n\) số nguyên: với mỗi nút \(1, 2, \ldots, n\), in ra số lượng màu khác nhau

Example

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

3 1 2 1 1