Most Frequent Character

Given a string s consisting of lowercase English letters, your task is to find the character that occurs most frequently in the string. In the event of a tie (i.e. multiple characters have the same highest frequency), return the character that appears first in s.

Note: The frequency of a character is the number of times it appears in the string. In case of a tie, the first-occurring character (i.e., with the smallest index) among the ones with the maximum frequency should be returned.

Mathematically, if we denote by \( f(c) \) the frequency of a character \( c \) in the string, then we want to find the character \( c^* \) such that:

[ c^* = \min{ c \mid f(c) = \max{ f(x) : x \in s } } ]

where the \( \min \) is taken over the indices at which the characters occur.

inputFormat

The input consists of a single line containing a non-empty string ( s ) composed only of lowercase English letters.

outputFormat

Output a single character, which is the most frequent character in the string ( s ). In case of a tie, output the character that appears first in the string.## sample

aabbbccde

b