Power of Power

時間制限 : 2 sec, メモリ制限 : 65536 KB

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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2011 , Day 2, Tokyo, Japan, 2011-09-18
http://acm-icpc.aitea.net/