Problema número 510

Marketing de zapatos

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Par de zapatos rojos de tacón vistos desde detrás

En la zapatería donde trabajo para sacarme unas perrillas tenemos dos modelos de zapatos distintos (uno para hombre y otro para mujer) a los que prestamos especial atención porque se venden muy bien en estas fechas. Para intentar cautivar a los clientes, la responsable de escaparatismo (o "visual merchandising", como le gusta decir a ella que es muy cool) ha decidido colocar un montón de ejemplares de esos dos tipos de zapatos a lo largo de la pared principal de la tienda en una fila enorme.

Hay que reconocer que tiene buen gusto, porque la forma en la que ha alternado los dos modelos crea una mezcla de color muy atrayente y las ventas han subido aún más. Pero se nota que no es ella quien se encarga de atender a los clientes, porque los zapatos no están ordenados por talla, y cada vez que tenemos que buscar una nos toca pasearnos de un lado a otro por toda la tienda.

Los vendedores queremos reordenar la fila de modo que la alternancia entre los dos modelos de zapatos se mantenga, pero, por separado, cada modelo esté ordenado por talla. Así no se perjudica al visual merchandising, pero son más fáciles de buscar.

Entrada

La entrada consiste en múltiples casos de prueba. Cada uno comienza con un número 1 ≤ N ≤ 1.000 indicando el número de zapatos puestos en la fila de la tienda. La línea siguiente contiene N números con las tallas de todos ellos en su disposición original.

Para diferenciar entre los dos modelos, las tallas de uno de ellos se proporcionan con números positivos, y las tallas del otro con números negativos. Somos una zapatería que está dentro de la iniciativa perfect fit de ajuste perfecto, por lo que, en valor absoluto, las tallas son números entre 1 y 1.000.

La entrada termina con un caso sin zapatos, que no debe procesarse.

Salida

Por cada caso de prueba se escribirá la lista de tallas de zapatos reordenada de menor a mayor. Las tallas se escribirán también con valores positivos y negativos como en la entrada. Por el especial significado del signo, en la salida los números positivos estarán ordenados de menor a mayor, y los negativos de mayor a menor.

Entrada de ejemplo

4
32 -32 -30 30
6
50 40 -70 50 -30 -70
0

Salida de ejemplo

30 -30 -32 32
40 50 -30 50 -70 -70