String Rearrangement

In this problem, 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. If such a rearrangement is possible, output one valid rearranged string; otherwise, output (-1).

For example, if (S = \texttt{aab}), one valid rearrangement is (\texttt{aba}). However, if (S = \texttt{aaab}), there is no valid rearrangement, so you should output (-1).

The problem can be approached with a greedy algorithm using a max-heap (priority queue) to always select the character with the highest remaining frequency that is not the same as the previously placed character.

inputFormat

Input is read from standard input (stdin). The input consists of a single line containing the string (S), where (S) contains only lowercase English letters.

outputFormat

Output a single line to standard output (stdout) containing a rearranged string such that no two adjacent characters are the same. If no valid rearrangement exists, output (-1).## sample

aab

aba