Trang trại T có \(N\) con bò bất tử. Để dễ dàng quản lý trang trại, Tade - chủ trang trại - đã nhập về rất nhiều chuồng bò để xếp những con bò cùng tuổi vào một chuồng. Tuy nhiên, vì quyển số ghi chép đàn bò của Tade bị bò gặm mất từ tháng trước nên anh ấy đã mất hết dữ liệu về số lượng con bò của mỗi nhóm tuổi. Do đó, các bạn hãy giúp Tade đếm xem có bao nhiêu con bò trong mỗi số tuổi từ \(1\) đến \(K\) nhé!

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N, K\) \((1 \le N \le 10^5, 1 \le K \le 10^6)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) \((1 \le a_i \le K)\) - tuổi của từng con bò trong trang trại.

Output

• In ra \(K\) dòng theo định dạng <tuổi>: <số lượng>

Example

8 5
1 1 4 3 2 3 4 3

1: 2
2: 1
3: 3
4: 2
5: 0