Consideremos la siguiente transformación de cadena:

1. Añadir el carácter # a la cadena (suponemos que # es lexicográficamente menor que todos los demás caracteres).
2. Generar todas las rotaciones de la cadena.
3. Ordenar las rotaciones de forma ascendente.
4. Según este orden, construir una nueva cadena que contenga el último carácter de cada rotación.

Por ejemplo, la cadena ~babc~ se convierte en babc#. La lista ordenada de rotaciones es #babc, abc#b, babc#, bc#ba y c#bab. Esto da como resultado la cadena cb#ab.

Entrada

La única línea de entrada contiene la cadena transformada de longitud ~n+1~. Cada carácter de la cadena original es uno de los caracteres de la a a la z.

Salida

Imprimir la cadena original de longitud ~n~.

Restricciones

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

Ejemplo de Entrada

cb#ab

Ejemplo de Salida

babc