Problem Background

This problem is an adapted version.

Problem Description

Tweetuzki has a sequence of length \( n \), denoted as \( a_1, a_2, \cdots, a_n \).

He wishes to find the largest \( k \) such that there exists a subsequence \( b_1, b_2, \cdots, b_k \) (whose elements can be rearranged from the original sequence) satisfying the condition that for any \( i \) (where \( 1 \le i < k \)), \( 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} \). He also wants to output this subsequence.

Input Format

The first line contains a positive integer \( n \) (where \( 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 \) (where \( 1 \le a_i \le 3 \times 10^{18} \)), describing the sequence.

Output Format

The first line contains a positive integer \( k \), representing the largest \( k \).
The second line contains \( k \) positive integers \( b_1, b_2, \cdots, b_n \), describing the chosen subsequence.

Sample Input and Output

Sample Input #1

6
4 8 6 3 12 9

Sample Output #1

6
9 3 6 12 4 8

Sample Input #2

4
42 28 84 126

Sample Output #2

4
126 42 84 28

Sample Input #3

5
4 8 16 12 24

Sample Output #3

4
12 24 8 16

Notes

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 \).

见题面 Input 部分

见题面 Output 部分