Rearrange String to Avoid Adjacent Duplicates

Given a string s, rearrange its characters such that no two adjacent characters are the same. In other words, if s = s₁s₂...s_n, you need to obtain a permutation t = t₁t₂...t_n satisfying \(t_i \neq t_{i+1}\) for all \(1 \leq i < n\).

If there are multiple valid rearrangements, output any one of them. If no valid rearrangement exists, output "-1".

Note: Any formula used in the description is formatted in \(\LaTeX\). Ensure that your solution reads input from standard input and writes the result to standard output.

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output a single line: the rearranged string where no two adjacent characters are identical, or "-1" if no valid rearrangement exists.

aab

aba