Tèo được giao nhiệm vụ quản lý thông tin của một dòng tộc lớn có cấu trúc dạng cây gồm \(N\) thành viên được đánh số từ \(1\) đến \(N\) (thành viên \(1\) là người khởi tổ). Mỗi thành viên \(i\) có một màu sắc yêu thích được biểu diễn bằng một số nguyên dương.

Với mỗi thành viên \(u\), Tèo cần thống kê xem trong toàn bộ các hậu duệ thuộc gia tộc của \(u\) (tính cả chính \(u\)), có bao nhiêu màu sắc yêu thích phân biệt xuất hiện đúng \(K\) lần.

Hãy viết chương trình hỗ trợ Tèo thống kê dữ liệu dòng tộc cực kỳ lớn này.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le N \le 5 \cdot 10^4\), \(1 \le K \le N\)).
• Dòng hai chứa \(N\) số nguyên, số thứ \(i\) là màu sắc yêu thích của thành viên thứ \(i\) (\(1 \le color_i \le N\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u, v\) mô tả mối quan hệ trực hệ giữa hai thành viên trong cây dòng tộc (\(1 \le u, v \le N\)).

Định dạng đầu ra

• In ra \(N\) số nguyên trên một dòng cách nhau bởi dấu cách, số thứ \(u\) là số lượng màu sắc xuất hiện đúng \(K\) lần trong gia tộc của thành viên \(u\).

Ví dụ

Input:

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

Output:

1 2 1 1 1