Soma de Prefixo: Primos

Nós estávamos dando de presente belas mochilas contendo pedacinhos de papel com números escritos! Uma mochila que queremos dar de presente para você contém $n$ pedacinhos de papel. Cada um deles tem um inteiro escrito nele: $1$ ou $2$.

Mesmo assim, existe uma condição que você deve satisfazer para receber o prêmio. Você vai precisar colocar todos os pedacinhos de papel da mochila em sequência, da maneira que você desejar. Nós iremos computar as somas de todos os prefixos desta sequência, e então contaremos quantas destas somas são números primos. Se você quer o presente, você deverá maximizar o número de números primos que você conseguiu formar.

Você conseguirá o prêmio? Corra, as mochilas estão esperando!

Entrada

A primeira linha da entrada contém um inteiro $n$ $(1\leq n \leq 200.000)$- o número de pedacinhos de papel na mochila. A próxima linha contém $n$ inteiros $a_1, a_2, ..., a_n$ , cada um deles sendo $1$ ou $2$, os valores escritos nos papéis.

Saída

Imprima uma permutação $b_1, b_2, ..., b_n$ da sequência da entrada, maximizando o número de somas de prefixos sendo números primos. Se existirem múltiplas permutações
ótimas, imprima qualquer uma delas.

Exemplo de Entrada 1

5 1 2 1 2 1

Exemplo de Saída 1

1 1 1 2 2

Exemplo de Entrada 2

9 1 1 2 1 1 1 2 1 1

Exemplo de Saída 2

1 1 1 2 1 1 1 2 1