Tweetuzki's Sequence Subsequence

Tweetuzki has a sequence of length \(n\): \(a_1, a_2, \ldots, a_n\). He wants to find the longest possible subsequence \(b_1, b_2, \ldots, b_k\) taken from the given sequence (the order in the original sequence may be changed) such that for every \(1 \le i < k\) one of the following holds:

• \(b_i\) is divisible by \(3\) and \(\frac{b_i}{3} = b_{i+1}\), or
• \(b_i \times 2 = b_{i+1}\).

If there are multiple valid answers, output any one of them. It is guaranteed that a solution exists.

inputFormat

The first line contains an integer \(n\) (the length of the sequence). The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\).

outputFormat

Output the elements of the found subsequence \(b_1, b_2, \ldots, b_k\) in order, separated by spaces.

sample

6
4 8 6 3 12 9

9 3 6 12 4 8