Se puede generar una rotación de una cadena moviendo caracteres uno tras otro de principio a fin. Por ejemplo, las rotaciones de acab son ~acab, caba, abac~ y ~baca~.

Su tarea es determinar la rotación lexicográficamente mínima de una cadena.

Entrada

La única línea de entrada contiene una cadena de longitud ~n~. Cada carácter es uno de ~a-z~.

Salida

Imprima la rotación lexicográficamente mínima.

Restricciones

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

Ejemplo de Entrada

acab

Ejemplo de Salida

abac