Code Submission Evaluation System Login

CSES Problem Set

String Reorder


Task | Statistics


CSES - String ReorderCSES - String Reorder

Time limit:1.00 s Memory limit:512 MB

Given a string, you want to reorder its characters so that no two adjacent characters are the same. What is the lexicographically minimal such string?

Input

The only input line as a string of length $n$ consisting of characters A–Z.

Output

Print the lexicographically minimal reordered string where no two adjacent characters are the same. If it is not possible to create such a string, print $-1$.

Constraints
Example

Input:
HATTIVATTI

Output:
AHATITITVT