Sort Characters by Frequency

Given a string s, rearrange its characters such that the characters with higher frequency appear before those with lower frequency. If two characters have the same frequency, they should appear in the same order as they do in the original string (i.e., the order of their first occurrence is preserved).

For example, for the input tree, the character 'e' appears twice while 't' and 'r' appear once; hence, the output should begin with the two 'e's followed by 't' and 'r' in the order they originally appeared, resulting in eetr.

You are required to read the input from standard input (stdin) and print the result to standard output (stdout).

Note: In all provided solutions, the input is read entirely from stdin, processed, and the answer is printed to stdout.

inputFormat

The input consists of a single line, which is the string s. The string may contain letters, digits, or other characters. If the string is empty, output an empty string.

outputFormat

Output a single line containing the rearranged string according to the frequency sorting rule: characters sorted in descending order by frequency and preserving the original order when frequencies are equal.

tree

eetr