Count the frequency of every word in a line. Matching is case-insensitive, and punctuation is ignored. Print words in alphabetical order.</p>

Input

The input contains one line s (1 ≤ |s| ≤ 1000000). A word is a maximal non-empty sequence of ASCII letters A–Z or a–z.

Output

For each distinct lowercase word, print word: frequency on its own line, in alphabetical order.

Examples

Input #1

Hello hello world

Output #1

hello: 2
world: 1

Explanation #1: After converting to lowercase, hello occurs twice and world occurs once. The output is alphabetical.

Input #2

Pear, apple! PEAR; plum apple.

Output #2

apple: 2
pear: 2
plum: 1

Explanation #2: Punctuation is removed and letter case is ignored, so Pear and PEAR represent the same word.