Problem Description

Given a string, sort its characters by their frequency in descending order (most frequent first). If two characters have the same frequency, maintain their original relative order.

Input Format

A single string containing any characters.

Output Format

A string with characters sorted by frequency (highest first), maintaining relative order for equal frequencies.

Constraints

• 1 ≤ string length ≤ 1000

• String can contain any ASCII characters

• Maintain relative order for characters with same frequency

• Case-sensitive comparison

Sample Input/Output

tree

eert

Explanation

Character frequencies: 'e' appears 2 times, 't' and 'r' each appear 1 time. So 'e' comes first (ee), then 't' and 'r' in their original order (tr).