Sort Words by Frequency

The Riverbend Gazette builds a word cloud from the day's headlines, and the cloud is drawn from a ranked list: the most used word at the top, the least used at the bottom. Words used exactly as often as each other are ranked by which one the newsroom printed first that day, so that running the tool twice on the same feed always draws the same cloud — designers had complained that the ranking moved between builds.

Task: Print each distinct word with how many times it was used, most used first.

Input

A single line holding between 1 and 1000 lowercase words separated by single spaces.

Output

One line per distinct word: the word, a colon, then its count, with no spaces anywhere. Lines run from the highest count down to the lowest. Words on the same count keep the order in which they first appeared in the line.

Example:

Input:
the cat sat on the mat the cat

Output:
the:3
cat:2
sat:1
on:1
mat:1