Cho số nguyên dương ~N~ và dãy gồm ~N~ số nguyên ~a_1, a_2,...,a_n~.

Yêu cầu: In ra các phần tử cùng với số lần xuất hiện của nó

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương ~N~(~1 \le N \le 10^5~)
• Dòng thứ 2: Ghi ~N~ số nguyên ~a_1, a_2,...,a_n~(~1 \le a_i \le 10^9~).

Kết quả:

• Gồm ~N~ dòng, mỗi dòng gồm 2 số lần lượt là giá trị ~a_i~ và số lần xuất hiện của nó trong dãy.

Ví dụ:

Input

9
1 1 2 4 6 6 6 6 7

Output

1 2
2 1
4 1
6 4
7 1

Ràng buộc:

• Có 50% số test ~1 ≤a_i ≤ 10^6~;
• Có 50% số test ~1 ≤ a_i ≤ 10^9~;