Reorganize String

You are given a string S consisting of lowercase letters. Your task is to rearrange the characters of S so that no two adjacent characters are the same. In other words, if the rearranged string is denoted as T, then for all valid indices i, it must hold that \(T[i] \neq T[i+1]\). If no such rearrangement exists, output an empty string.

Examples:

• For S = "aab", one possible answer is "aba".
• For S = "aaab", no valid rearrangement exists, so the output is an empty string.

It is guaranteed that the input string consists of only lowercase English letters.

inputFormat

The input consists of a single line containing the string S (only lowercase alphabets).

outputFormat

Output a rearranged string that satisfies the condition \(T[i] \neq T[i+1]\) for all valid indices. If no such rearrangement is possible, output an empty string.

aab

aba