Frequency Sorting of Characters

Given a string s consisting of lowercase alphabets, rearrange the characters such that they are sorted by their frequency in descending order. In other words, for two characters c₁ and c₂, if \( f(c_1) > f(c_2) \) then c₁ should appear before c₂. If the frequencies are equal, then sort the characters in ascending lexicographical order.

Note: Here, \( f(c) \) denotes the number of occurrences of character c in the string s.

inputFormat

The input consists of a single line containing a non-negative string of lowercase English letters.

outputFormat

Output a single line, which is the input string rearranged such that characters are sorted by their frequency in descending order. For characters with the same frequency, they should appear in alphabetical order.

tree

eert