Divide by 3, Multiply by 2

Interview

Time limit2sMemory limit512 MB

Summary

Given a shuffled copy B of the sequence produced by a divide-by-3, multiply-by-2 game, reconstruct the original order A.

Level: Medium5 of 10
Topics: Graph, DFS, Hash map, Math
Solved: No attempts yet

Problem

The divide-by-3, multiply-by-2 game uses a single integer. Start with an integer $x$ and apply an operation $N-1$ times. There are two operations available.

Divide by 3: divide $x$ by 3. $x$ must be divisible by 3.
Multiply by 2: multiply $x$ by 2.

Recording every number produced while playing the game gives a sequence $A$ . For example, if $x = 9$ , $N = 6$ , and the operations applied are multiply by 2, multiply by 2, divide by 3, multiply by 2, divide by 3, then $A = [9, 18, 36, 12, 24, 8]$ .

Given a sequence $B$ obtained by shuffling the order of $A$ , find $A$ .

Input

The first line contains the size of the sequence $N(2 \le N \le 100)$ . The second line contains the sequence $B$ . Each element of $B$ is a positive integer less than or equal to $10^{18}$ .

Output

Output the sequence $A$ produced by the divide-by-3, multiply-by-2 game. The input is given only when a solution always exists; if there are multiple valid answers, output any one of them.

Examples2

Example 1
Input
```
6
4 8 6 3 12 9
```
Expected output
```
9 3 6 12 4 8
```
Example 2
Input
```
4
42 28 84 126
```
Expected output
```
126 42 84 28
```