印出考拉茲數列

題目敘述

小明在課堂上玩一個數字遊戲：先寫下一個正整數 n，然後不斷依規則改寫手上的數字。

• 如果目前的數是偶數，就把它換成 n/2；
• 如果目前的數是奇數，就把它換成 3n+1。

一直做到數字變成 1 為止。請依序印出整個過程中出現過的所有數字，第一個是最初的 n，最後一個是 1。

輸入格式

• 一個整數 n。

輸出格式

• 一行，依出現順序列出所有數字，以空格分隔。

限制

• 1 ≤ n ≤ 10⁶

範例

範例 1

輸入

3

輸出

3 10 5 16 8 4 2 1

說明

3 是奇數，變成 10；10 是偶數，變成 5；5 是奇數，變成 16；之後依序是 8,4,2,1。

範例 2

輸入

1

輸出

1

說明

一開始就是 1，所以只有這一個數字。

說明

• 即使 n ≤ 10⁶，過程中的數字仍可能超過 2³¹−1，請使用 64 位元整數。