- Time limit: 1.00 s
- Memory limit: 512 MB
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
- $1 \le n \le 10^6$
Input:
HATTIVATTI
Output:
AHATITITVT