Problem Description

Given a positive integer $n$, keep doing the following operation on this number: if the number is odd, multiply it by $3$ and then add $1$; otherwise, divide it by $2$. After several cycles, it will always return to $1$. It has been verified that even very large numbers ($7\times 10^{11}$) can become $1$ in this way, so it is called the "Collatz Conjecture". For example, when $n$ is $20$, the process is $20\to 10\to 5\to 16\to 8\to 4\to 2\to 1$.

Given the number, verify this conjecture, and starting from the final $1$, output the entire sequence in reverse order.

Input Format

Input one positive integer $n$.

Output Format

Output several positive integers separated by spaces, representing the sequence in reverse order starting from the final $1$.

20

1 2 4 8 16 5 10 20

Hint

Constraints: it is guaranteed that $1 \le n\le 100$.

Translated by ChatGPT 5