Trong một cuộc điều tra khoa học, người ta thu được $n$ số tự nhiên, mỗi số đều không vượt quá $1.5 \times 10^9$. Biết rằng số lượng giá trị đôi một khác nhau không vượt quá $10^4$. Bây giờ cần thống kê số lần xuất hiện của từng số tự nhiên này và in kết quả thống kê theo thứ tự các số tự nhiên từ nhỏ đến lớn.

Dữ liệu vào

Gồm $n+1$ dòng.

Dòng đầu tiên là số nguyên $n$, cho biết số lượng số tự nhiên;

Từ dòng $2$ đến dòng $n+1$, mỗi dòng một số tự nhiên. Mỗi số đều không vượt quá $1.5×10^9$.

Dữ liệu ra

Gồm $m$ dòng ($m$ là số lượng giá trị khác nhau trong $n$ số tự nhiên), in theo thứ tự các số tự nhiên từ nhỏ đến lớn.

Mỗi dòng in $2$ số nguyên, lần lượt là số tự nhiên và số lần xuất hiện của số đó, cách nhau một dấu cách.

Ví dụ

Input

8
2
4
2
4
5
100
2
100

Output

8
2
4
2
4
5
100
2
100

Ghi chú

• $30\%$ số dữ liệu thỏa mãn: $1 \le n \le 1000$;
• $60\%$ số dữ liệu thỏa mãn: $1 \le n \le 50000$;
• $100\%$ số dữ liệu thỏa mãn: $1 \le n \le 200000$, mỗi số đều không vượt quá $1.5 \times 10^9$.

Bài đầu tiên bảng nâng cao NOIP 2007

Nguồn: NOIP 2007 bảng nâng cao