Rearranging Characters

You are given a string s consisting of lowercase English letters. Your task is to rearrange the characters of s so that no two adjacent characters are the same. In other words, for the resulting string t, the condition $$t[i] \neq t[i+1]$$ must hold for every valid index i. If no valid rearrangement exists, output an empty string.

inputFormat

The input is provided via standard input (stdin) as a single line containing the string s.

outputFormat

The output should be printed to standard output (stdout) as a rearranged string that satisfies the condition. If it is impossible to rearrange s, print an empty string.## sample

aab

aba