Xét thuật toán sau đây: nhập vào một số nguyên dương \(n\). Nếu \(n\) chẵn, ta thực hiện chia \(n\) cho \(2\). Ngược lại, nếu \(n\) lẻ, ta nhân \(n\) lên \(3\) lần rồi cộng cho \(1\). Thuật toán được lặp lại cho đến khi giá trị của \(n\) trở thành \(1\). Ví dụ, nếu \(n=3\) thì ta sẽ thu được dãy số sau nếu thực hiện thuật toán trên:

\(3\rightarrow 10\rightarrow 5\rightarrow 16\rightarrow 8\rightarrow 4\rightarrow 2\rightarrow 1\)

Bạn hãy lập trình mô phỏng lại việc thực hiện thuật toán được mô tả ở trên nhé!

Input

• Một dòng duy nhất chứa số nguyên dương \(n\) \(\left(n \leq 10^6\right)\).

Output

• In ra một dòng chứa tất cả các giá trị của \(n\) trong quá trình thực hiện thuật toán trên.

Ví dụ

Sample input 01

3

Sample output 01

3 10 5 16 8 4 2 1