Counting Numbers

Problem Description

During a scientific survey, $n$ natural numbers were obtained, each not exceeding $1.5 \times 10^9$. It is known that there are at most $10^4$ distinct numbers. Now we need to count how many times each natural number appears, and output the statistics in increasing order of the natural numbers.

Input Format

There are $n+1$ lines in total.

The first line is the integer $n$, the number of natural numbers.

Lines $2$ through $n+1$ each contain one natural number.

Output Format

There are $m$ lines in total ($m$ is the number of distinct numbers among the $n$ natural numbers), output in increasing order of the natural numbers. Each line outputs two integers: the natural number and how many times it appears, separated by a single space.

Sample Input

8
2
4
2
4
5
100
2
100

Sample Output

2 3
4 2
5 1
100 2

Hint

• $30\%$ of the data: $1 \le n \le 1000$;
• $60\%$ of the data: $1 \le n \le 50000$;
• $100\%$ of the data: $1 \le n \le 200000$, each number not exceeding $1.5 \times 10^9$.

NOIP 2007, improvement group, problem 1.