Sort Characters By Frequency

You are given a string s of lowercase English letters. Rebuild the string so that characters appearing more often are placed before characters appearing less often. When two distinct characters appear the same number of times, the alphabetically smaller character is placed first. Each character is repeated as many times as it occurs in s.

Because the tie-break is fully specified, exactly one output string is correct.

Input format

Line 1: the string s (lowercase letters, no spaces).

Output format

One line: the rearranged string.

Constraints

• 1 <= length of s <= 100000
• s contains only the characters a-z