Read an entire text, count words case-insensitively while ignoring punctuation, and print at most five most frequent words. Ties are resolved alphabetically.</p>

Input

The input contains one or more lines of text with total length at most 1000000. A word is a maximal sequence of ASCII letters.

Output

Print each result as word: frequency, ordered by decreasing frequency and then alphabetically.

Examples

Input #1

I love coding. Coding is fun!

Output #1

coding: 2
fun: 1
i: 1
is: 1
love: 1

Explanation #1: coding occurs twice. The remaining words occur once, so the first four alphabetically are fun, i, is, and love.

Input #2

Red blue red. BLUE green; red!

Output #2

red: 3
blue: 2
green: 1

Explanation #2: red occurs three times, blue twice, and green once after lowercase conversion and punctuation removal.