Description

You are studying to become the next best rapper in South Korea, so you started watching the rapper TV show and study the rappers. The way you study is you count how many times each word appears in the transcript. However, since you are lazy but smart, you decided to code an algorithm that can count them for you from the transcript passed to you.

Here are the methods of counting:

• The transcript is given as one single line.
• Counting is case-insensitive (i.e. Yo, YO, and yo are the same word. Output words in lowercase).
• The characters . , ! ? are treated as separators, the same as whitespace. So flow,rhyme counts as two words.
• Any other character (including ' and -) is part of the word. don't stays don't.
• Words are separated by whitespace and/or the punctuation above.
• If the line contains no words, print EMPTY.

You need to output the word and the frequency of it, sorted by the frequency descending.

Input

One line containing the transcript. Length ≤ 1000 characters.

Output

One line per distinct word, in the format <word> <frequency> , sorted by frequency in descending order. If two words have the same count, sort them in lexicographic (ASCII) order, ascending. Note that ' and - come before letters in ASCII, so don't comes before dont.

Sample Input  Download

Sample Output  Download

Tags

Discuss