Sort Characters by Frequency

Given a string s, your task is to rearrange its characters such that they are sorted primarily by their frequency in descending order and secondarily by their lexicographical order (in ascending order) when frequencies are equal.

Let \( f(c) \) denote the frequency of character \( c \) in the string. The ordering of characters should satisfy the following:

[ \text{For two characters } c_1 \text{ and } c_2,\quad \text{if } f(c_1) \neq f(c_2), \text{ then } f(c_1) > f(c_2). \quad \text{Otherwise, } c_1 < c_2 \ (\text{in lexicographical order}). ]

For example, for the string "tree", the character 'e' appears twice and should come first, while 'r' and 't' each appear once and should be sorted as "r" then "t", resulting in "eert".

inputFormat

The input consists of a single line containing the string s. The string can contain any ASCII characters. Note that the empty string is also a valid input.

outputFormat

Output a single line containing the rearranged string according to the rules specified: characters sorted by descending frequency and then by ascending lexicographical order if frequencies are equal.

tree

eert