Sort Characters by Frequency

You are given a string consisting of letters (and possibly other characters). Your task is to sort the characters in the string according to their frequency in descending order. In the event of a tie (i.e. characters with the same frequency), they should be arranged in alphabetical order (according to their ASCII value). For instance, given the input tree, the character e appears twice while r and t appear once, so the correctly sorted result is eert.

The sorting rule is formally given by:

\(\text{For any two characters } a \text{ and } b,\ \text{if } f(a)=f(b) \text{ then } a f(b)\)

where \(f(x)\) denotes the frequency of character \(x\) in the string.

Make sure your solution reads input from stdin and writes the output to stdout without any extra formatting.

inputFormat

The input consists of a single line containing a non-empty string.

Note: The string may include both uppercase and lowercase letters and is read from standard input.

outputFormat

Output the sorted string according to the rules described above to standard output.

tree

eert