F: Power of Power

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

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

N 個の非負整数 A₁, A₂, ..., A_N がある．これらの並べ替え B₁, B₂, ..., B_N であって，B₁^{B₂...B_{N - 1}B_N} が最大になるものを求めたい．うさぎたちにとってはもちろん常識であるが，この計算は右上から順に行う．また，0⁰ = 1 であると約束することにする．

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

Input

N
A1
 ...
AN

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

Output

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

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