Analyze frequencies of the lowercase letters that occur in a string.

Input

The input contains one nonempty string s consisting only of lowercase English letters.

$1 \le |s| \le 10^6$; every character is a lowercase English letter.

Output

Print three lines: the most frequent letter and its frequency (ties choose the smallest letter); the least frequent occurring letter and its frequency (ties choose the largest letter); and the number of distinct letters.

Example

Input

abacabad

Output

a 4
d 1
4