Thuật toán kỳ lạ

Nguồn: CSES Problem Set

Đề bài

Xét một thuật toán nhận đầu vào là một số nguyên dương $n$.

Thuật toán được thực hiện như sau:

• Nếu $n$ là số chẵn, thay $n$ bằng $\dfrac{n}{2}$.
• Nếu $n$ là số lẻ, thay $n$ bằng $3n+1$.

Lặp lại quá trình trên cho đến khi $n=1$.

Ví dụ, với $n=3$, ta thu được dãy:

$$3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$

Nhiệm vụ của bạn là mô phỏng thuật toán trên với giá trị $n$ đã cho và in ra toàn bộ các giá trị xuất hiện trong quá trình thực hiện.

Dữ liệu vào

Dòng duy nhất chứa một số nguyên dương $n$.

Dữ liệu ra

In ra trên một dòng tất cả các giá trị của $n$ xuất hiện trong quá trình thực hiện thuật toán, theo đúng thứ tự.

Các giá trị được phân cách bởi một dấu cách.

Giới hạn

• $1 \le n \le 10^6$

Ví dụ

Input

3

Output

3 10 5 16 8 4 2 1