Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example 1:

Input:  tree
Output: eert

("eetr" is also valid)

Example 2:

Input:  cccaaa
Output: aaaccc

("cccaaa" is also valid)

Example 3:

Input:  Aabb
Output: bbAa

Constraints:

• 1 ≤ s.length ≤ 5 × 10⁵

Input format: A single string.

Output format: The sorted string.