Frequency of Elements, in First-Seen Order

Riverbend Council counts a ballot by drawing papers from the box one at a time and calling out the candidate number on each. The tally sheet lists the candidates in the order they were first called, not by how well they did, because the observers standing at the table follow the sheet as it is written and a sheet that reorders itself mid-count is impossible to check.

Task: Print each candidate number with the number of papers that carried it.

Input

A single line holding between 1 and 1000 integers separated by single spaces — the candidate numbers in the order the papers came out of the box.

Output

One line per distinct candidate: the candidate number, a colon, then the count, with no spaces anywhere. The lines follow the order in which each candidate was first called.

Example:

Input:
4 4 2 4 3 2

Output:
4:3
2:2
3:1