Descripción

La competencia "Granjero del Año". En esta competencia cada granjero organiza sus vacas en una fila y las hace desfilar ante el jurado.

Los organizadores de la competencia adoptaron un nuevo sistema de registro este año: simplemente registrar la primera letra de cada vaca en el orden en que ellas aparecerán (por ejemplo, si FJ lleva a Bessie, Sylvia, y Dora en ese orden, el simplemente registra BSD). Después que termina la fase de registro, cada grupo es juzgado en orden lexicográfico creciente (esto es, orden alfabético similar al de un diccionario) de acuerdo a la cadena de las iniciales de los nombres de las vacas.

GJ está muy ocupado este año y quiere volver rápido a su granja, por lo tanto él quiere pasar delante de los jurados tan temprano como sea posible. El decide reorganizar sus vacas, las cuales ya están en una fila, antes de registrarlas.

GJ encuentra un lugar para una nueva fila de las vacas competidoras.

Luego él procede a hacer marchar las vacas de la fila vieja a la nueva enviando repetidamente o la primera vaca o la última vaca de la fila original (lo que queda de ella) al final de la fila nueva. Cuando él ha terminado, él lleva sus vacas para registrarlas en este nuevo orden.

Tarea

Dado el orden inicial de sus vacas, determine la cadena lexicográficamente menor quepuede hacerse de esta manera.

Entrada

• Línea 1: un solo entero: ~N~

• Líneas ~2..N+1~: La línea ~i+1~ contiene una sola inicial ~('A'..'Z')~ de la vaca en la posición iésima en la fila original.

Ejemplo de Entrada

6
A
C
D
B
C
B

Detalles de la entrada

GJ tiene ~6~ vacas en este orden: ~ACDBCB~

Salida

La cadena menor lexicográficamente que se puede hacer. Cada línea (excepto tal vez la última) contiene las iniciales de 80 vacas ~('A'..'Z')~ en la fila nueva.

Ejemplo de Salida

ABCBCD

Detalle de la salida

Paso Original Nueva

1 ACDBCB

2 CDBCB A

3 CDBC AB

4 CDB ABC

5 CD ABCB

6 D ABCBC

7 ABCBCD