Character Frequency Map

Read a string. Print each character and its frequency, one per line, in order of first appearance.

Your task

Write a complete program: read the input with input() and print the result with print().

Example

Input

hello

Output

h: 1
e: 1
l: 2
o: 1