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.