Background

This problem is an adapted problem.

Problem Description

Tweetuzki has a sequence $a_1, a_2, \cdots, a_n$ of length $n$.

He wants to find the maximum $k$ such that there exist some numbers $b_1, b_2, \cdots, b_k$ in the original sequence (not necessarily in the same order as in the original sequence), satisfying that for any $i(1 \le i < k)$, either $b_i \div 3 = b_{i+1}$ (in this case, $b_i$ must be divisible by $3$) or $b_i \times 2 = b_{i+1}$. Output this sequence as well.

Input Format

The first line contains a positive integer $n(2 \le n \le 10^5)$, representing the length of the sequence.
The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n(1 \le a_i \le 3 \times 10^{18})$, describing the sequence.

Output Format

The first line contains a positive integer $k$, representing the maximum $k$.
The second line contains $k$ positive integers $b_1, b_2, \cdots, b_k$, describing the numbers you chose.

6
4 8 6 3 12 9

6
9 3 6 12 4 8 

4
42 28 84 126

4
126 42 84 28 

5
4 8 16 12 24

4
12 24 8 16

Hint

Subtask #1 (20 points)：$2 \le n \le 8$；
Subtask #2 (30 points)：$2 \le n \le 100, 1 \le a_i \le 7 \times 10^8$；
Subtask #3 (20 points)：$2 \le n \le 1000, 1 \le a_i \le 1000$；
Subtask #4 (30 points)：$2 \le n \le 10^5, 1 \le a_i \le 3 \times 10^{18}$。

Translated by ChatGPT 5