Most Frequent Character

You are given a non-empty string s. Your task is to find the character that appears the most times in the string. In case of a tie, return the lexicographically smallest character.

More formally, let \(f(c)\) denote the number of times character \(c\) appears in s. You need to choose a character \(x\) such that \[ f(x)=\max_{c \in s} f(c), \] If there exist multiple characters \(c\) with \(f(c)=f(x)\), output the character with the smallest ASCII value.

Note: Input is provided via standard input (stdin) and the answer should be printed to standard output (stdout).

inputFormat

The input consists of a single line containing the string s.

Constraints:
1 \(\leq |s|\leq\) 10⁶.

outputFormat

Output a single character which is the most frequent character in the given string. If there is a tie, output the lexicographically smallest one.

a

a