Descripción

Hay ~N~ enteros escritos en un tablero. El ~i-~ésimo entero es ~A_{i}~.

Eduardo y Alejandro están jugando con estos enteros. En el juego ellos organizarán los enteros en una fila, de la siguiente manera:

• Primero, Eduardo organizará estos enteros como él desee.
• Luego, Alejandro intercambiará dos enteros adyacentes que sean coprimos. Esto lo hará tantas veces como él desee.

Asumimos que Eduardo jugará de forma óptima para que la secuencia final sea la menor lexicográficamente posible, y Alejandro jugará de forma óptima para que la secuencia final sea la mayor lexicográficamente posible. Tu tarea es encontrar la secuencia final que será obtenida como resultado de este juego.

Entrada

La primera línea de la entrada contiene un entero ~N~ (~1 \le N \le 2000~), el número de enteros en el tablero.

La segunda línea contiene los valores de los ~N~ enteros, ~A_{1}, A_{2}, \dots, A_{N}~ (~1 \le A_{i} \le 10^8~).

Salida

La única línea de la salida debe contener ~N~ enteros, la secuencia final obtenida.

Subtareas

• Subtarea 1: Para todo par (~i,j~) se cumple que ~A_i = A_j~ (~5~ puntos)
• Subtarea 2: Para todo ~1 \le i \le N~ se cumple que ~A_i = i~ (~15~ puntos)
• Subtarea 3: ~1 \le N \le 8~ (~15~ puntos)
• Subtarea 4: ~1 \le N \le 500~ (~20~ puntos)
• Subtarea 5: Sin restricciones adicionales (~45~ puntos)

Ejemplos

Entrada 1

5
1 2 3 4 5

Salida 1

5 3 2 4 1

Entrada 2

4
2 3 4 6

Salida 2

2 4 6 3

Notas

• Se dicen que dos enteros son coprimos o primos relativos siempre y cuando su máximo común divisor sea ~1~, por ejemplo, los pares (~2, 3~), (~6, 35~) y (~7, 4~) son coprimos, pero (~3, 6~), (~4, 12~) y (~9, 135~) no lo son.