Problem:


F: Power of Power

ICPC で良い成績を収めるには修行が欠かせない．うさぎは ICPC で勝ちたいので，今日も修行をすることにした．

今日の修行は，非常に大きな数の計算を行って，計算力をつけて意識を高めようというものである．大きい数が簡単に出てくる演算として，累乗が挙げられる．

N 個の非負整数 A1, A2, ..., AN がある．これらの並べ替え B1, B2, ..., BN であって，B1B2...BN - 1BN が最大になるものを求めたい．うさぎたちにとってはもちろん常識であるが，この計算は右上から順に行う．また，00 = 1 であると約束することにする．

最大条件を満たす B1, B2, ..., BN は複数通りあるかもしれない．そのような場合は，そのうちで辞書順最小の列を選ぶことにしよう．

Input

N
A1
 ...
AN

1 ≤ N ≤ 100，0 ≤ Ai ≤ 1,000,000,000 を満たす．

Output

出力は N 行からなる．i 行目には Bi を出力せよ．

Sample Input 1

4
7
5
10
6

Sample Output 1

5
6
7
10

Sample Input 2

3
0
0
1000000000

Sample Output 2

1000000000
0
0



Sample input:
4
7
5
10
6


Sample output:
5
6
7
10

Submission status: Accepted

Solution code:
from collections import Counter
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def check(N, A):
    if N == 1:
        return A
    A.sort()

    C = Counter(A)
    c0 = C.get(0, 0)
    if c0 == N:
        return A
    c1 = C.get(1, 0)
    rest = A[c0+c1:]
    back = []
    if c0 > 0:
        if c0 % 2 == 0:
            back = [0]*c0 + [1]*c1
        else:
            if c1 > 0:
                x = 1
                c1 -= 1
            else:
                x, *rest = rest
            back = [0]*(c0 ^ 1) + [x] + [0] + [1]*c1
    else:
        back = [1]*c1
    if len(rest) >= 2 and rest[-1] == 3 and rest[-2] == 2:
        rest[-1], rest[-2] = rest[-2], rest[-1]
    return rest + back
def solve():
    N, *A = map(int, open(0).read().split())
    ans = check(N, A)
    write("\n".join(map(str, ans)))
    write("\n")
solve()