Công ty Alpha có ~ n ~ nhân viên được đánh số thứ tự từ 1 đến ~ n ~. Mỗi tháng trong năm công ty tổ chức tặng quà sinh nhật cho tất cả các nhân viên của mình sinh trong tháng đó.

Yêu cầu: Cho biết nhân viên thứ ~ i (i=1..n) ~ của công ty được sinh vào tháng ~ t_i ~. Bạn hãy giúp công ty tính số lượng món quà cần mua cho mỗi tháng trong một năm.

Dữ liệu vào

• Dòng đầu ghi số nguyên dương ~ n ~.
• Dòng thứ hai ghi ~ n ~ số nguyên, với số thứ ~ i ~ là ~ t_i (i = 1..n) ~ là tháng sinh của nhân viên thứ ~ i ~. Các số trên cùng dòng được ghi cách nhau một dấu cách.

Kết quả

Ghi theo từng dòng, với mỗi dòng gồm hai số nguyên, số đầu là tháng trong năm, số thứ hai là số món quà cần mua cho tháng đó, hai số cách nhau một dấu cách. Chỉ số tháng trên các dòng theo thứ tự tăng dần, chỉ số tháng nhỏ ghi ở dòng trước, chỉ số tháng lớn hơn ghi ở dòng sau.

Ràng buộc

• ~1 ≤ n ≤ 10^6 ~
• ~ 1 ≤ t_i ≤ 12 ~

Ví dụ:

Input 1

10
1 3 1 3 4 3 11 9 11 4 

Output 1

1 2
3 3
4 2
9 1
11 2