Frequency Sort

You are given a string s. You need to rearrange the characters of s so that characters with higher frequencies appear before those with lower frequencies. If two characters have the same frequency, they should be ordered in ascending lexicographical (alphabetical) order. Formally, let \( f(c) \) denote the frequency of character \( c \) in the string. Then for any two characters \( c_1 \) and \( c_2 \), \( c_1 \) should come before \( c_2 \) if either:

• \( f(c_1) > f(c_2) \), or
• \( f(c_1) = f(c_2) \) and \( c_1 < c_2 \) (in alphabetical order).

Your task is to implement this functionality.

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output the rearranged string according to the specified frequency and alphabetical ordering.## sample

banana

aaannb