P5080 Tweetuzki Loves Sequences

This problem is an adapted problem.

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.

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.

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.

**_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