Su tarea consiste en reordenar los caracteres de una cadena de modo que no haya dos caracteres adyacentes iguales. ¿Cuál es la cadena lexicográficamente mínima de este tipo?

Entrada

La única línea contiene una cadena de longitud ~n~ que consta de caracteres de la A a la Z.

Salida

Imprima la cadena reordenada lexicográficamente mínima donde no haya dos caracteres adyacentes iguales. Si no es posible crear dicha cadena, imprima -1.

Restricciones

• ~1 \leq n \leq 10^6~

Ejemplo de Entrada

HATTIVATTI

Ejemplo de Salida

AHATITITVT