Description

During a scientific survey, $n$ natural numbers were obtained, each not exceeding $1,500,000,000$ ($1.5 \times 10^9$). It is known that the number of distinct values does not exceed $10,000$. The task is to count the occurrences of each natural number and output the results in ascending order of the natural numbers.

Input Format

The first line contains an integer $n$, representing the number of natural numbers.
The next $n$ lines (lines 2 to $n+1$) each contain a natural number.

Output Format

The output consists of $m$ lines (where $m$ is the number of distinct natural numbers in the input), sorted in ascending order of the natural numbers. Each line contains two integers: the natural number and its occurrence count, separated by a space.

8
2
4
2
4
5
100
2
100

2 3
4 2
5 1
100 2

Hint

Data Range:

• 40% of the data satisfies: 1 ≤ n ≤ 1000;
• 80% of the data satisfies: 1 ≤ n ≤ 50000;
• 100% of the data satisfies: 1 ≤ n ≤ 200000, with each number not exceeding 1,500,000,000 (1.5 × 10^9^).

The use of STL and any related library calls is prohibited in this problem.