A scientific survey obtained ~n~ natural numbers, each one at most ~1\,500\,000\,000~ (~1.5 \times 10^9~).

We know that there are at most ~10\,000~ distinct numbers.

We want to count how many times each number appear, and output them in increasing order of the numbers.

Input Specification

Line ~1~ contains ~n~, the number of numbers, denoting the total number of numbers.

Lines ~2~ to ~n+1~ contain a number per line, denoting each number.

Output Specification

Output ~m~ lines (~m~ being the number of distinct numbers). Each contain two numbers, the value and the frequency.

Sample Input

8
2
4
2
4
5
100
2
100

Sample Output

2 3
4 2
5 1
100 2

Constraints

All data satisfy ~1 \le n \le 200\,000~, each number is at most ~1\,500\,000\,000~ (~1.5 \times 10^9~).

~40\%~ of the data satisfy ~1 \le n \le 10\,000~.

~80\%~ of the data satisfy ~1 \le n \le 50\,000~.