Arrange Characters by Frequency

Given a string s, arrange its characters such that they appear in decreasing order of their frequency. If two characters have the same frequency, they should be sorted in alphabetical order.

For example, given the input tree, the character 'e' appears twice while 't' and 'r' appear once. After sorting based on frequency and then alphabetically for ties, the output is eert.

The frequency sort can be defined mathematically as follows: if character c has frequency f(c), then for any two distinct characters a and b in s, a comes before b if and only if

\( f(a) > f(b) \) or \( f(a) = f(b) \text{ and } a < b \)

Read the string from standard input and output the rearranged string to standard output.

inputFormat

The input consists of a single line containing a non-negative string s. The string can be empty.

outputFormat

Output the string with its characters rearranged so that characters with higher frequency appear first. Characters with the same frequency should be output in alphabetical order.

tree

eert