CSES - 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

  • 1 \le n \le 10^6

Example

Input:

HATTIVATTI

Output:

AHATITITVT