Counting frequences P63414

Write a program that reads a sequence of natural numbers and that prints, for each one, how many times it appears.

Input

Input consists of a natural number $n$, followed by $n$ natural numbers between 1000000000 and 1000001000 (both included).

Output

For each number $x$ that appears in the sequence, print how many times it appears, following the format of the example. The output must be sorted in increasing order by $x$.