Trong một giờ học tại VP, cô Hương ra một đề bài như sau: Cho một cây ~N~ đỉnh, đánh số từ ~1~ đến ~N~, gốc tại ~1~, đỉnh ~i~ được tô màu ~a_i~. Yêu cầu đếm số lượng màu khác nhau trong cây con gốc ~i~ với mọi ~i~ từ ~1~ đến ~N~. Ví dụ cho cây ~6~ đỉnh như sau:

Với màu của các đỉnh lần lượt là: ~1, 2, 3, 4, 5, 6~. Xét cây con gốc ~4~, chứa ~4~ đỉnh: ~4, 2, 3, 5~. Vì thế nên cây con gốc ~4~ chứa ~4~ màu khác nhau.

Tuy nhiên, bài toán này quá khó với Huy. Các bạn hãy giúp Huy giải bài toán này nhé.

Dữ liệu

• Dòng đầu tiên chứa một số nguyên dương duy nhất ~N~ ~(N \le 2 \cdot 10^5)~.

• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ thể hiện một cạnh của cây.

• Dòng cuối cùng chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ ~(a_i \le 2 \cdot 10^5)~.

Kết quả

In ra ~N~ số nguyên trên một dòng là kết quả bài toán, số thứ ~i~ là kết quả của cây con gốc ~i~.

Ví dụ

Sample Input

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

Sample Output

6 1 1 4 1 1

Chấm điểm

• Subtask 1 (40% số test): ~1 \le N \le 10^3~.

• Subtask 2 (60% số test): Không có ràng buộc gì thêm.