Count non-whitespace characters in a line and print at most three characters with the highest frequencies. Ties are resolved by first appearance.</p>

Input

The input contains one line s (1 ≤ |s| ≤ 1000000). Whitespace is ignored; all other characters are case-sensitive.

Output

Print each selected result as character: frequency on a separate line.

Examples

Input #1

aaabbccccdde

Output #1

c: 4
a: 3
b: 2

Explanation #1: The frequencies are c = 4, a = 3, b = 2, d = 2, and e = 1. b wins the tie with d because b appears first.

Input #2

banana

Output #2

a: 3
n: 2
b: 1

Explanation #2: The three highest frequencies belong to a, n, and b; a and n tie and keep first-appearance order.