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