Power of Power

Time limit2sMemory limit512 MB

Summary

Given N integers, rearrange them so the power tower B1^(B2^(...^BN)) is maximized, and print the lexicographically smallest optimal order.

Level: Medium6 of 10
Topics: Greedy, Math, Sorting
Solved: No attempts yet

Problem

Good results at ICPC require training, so Usagi decided to train today in order to win at ICPC.

Today's training is to compute very large numbers, which builds calculation ability and raises awareness. Exponentiation is an operation that produces large numbers easily.

You are given $N$ non-negative integers $A_1, A_2, \ldots, A_N$ . Find a rearrangement $B_1, B_2, \ldots, B_N$ that maximizes $B_1^{B_2^{\cdots^{B_{N-1}^{B_N}}}}$ . This is common knowledge for the rabbits, but the evaluation proceeds from the top right. We define $0^0 = 1$ .

If several rearrangements achieve the maximum, output the lexicographically smallest one.

Input

N
A1
...
AN

$1 \le N \le 100$ , $0 \le A_i \le 1{,}000{,}000{,}000$ .

Output

The output consists of $N$ lines. The $i$ -th line prints $B_i$ .

Examples2

Example 1
Input
```
4
7
5
10
6
```
Expected output
```
5
6
7
10
```
Example 2
Input
```
3
0
0
1000000000
```
Expected output
```
1000000000
0
0
```