Reorganize String to Avoid Adjacent Duplicates

Given a string s, rearrange its letters to form a new string such that no two adjacent characters are the same. Among all possible valid rearrangements, output the lexicographically smallest one. If no valid rearrangement exists, output an empty string.

Note: The lexicographical order is defined in the usual way (i.e. dictionary order). For example, between two valid results "ababc" and "abcab", "ababc" is considered lexicographically smaller.

inputFormat

The input is given from standard input and consists of a single line containing the string s.

Constraints: The length of s is at least 0 and can include only lowercase English letters.

outputFormat

Print the reorganized string to standard output. If no valid rearrangement exists, print an empty string.

aabbc

ababc