菌の祖先

ヒデヨ博士は、新しい菌が増殖する様子を観察しています。１つの菌から子が生まれるときは同時に２つの菌が生まれます。一度子を生んだ菌は、二度と子を生むことはありません。ヒデヨ博士は、菌の増殖の過程を記録するために菌に番号を付けることにしました。最初、菌が１つだけのときはその菌に番号１を付けます。博士は、番号$i$の菌が子を生んだとき、それらに番号$2i$と$2i+1$を付ければ、すべての菌にそれぞれ異なる番号が付けられることに気づきました。この番号付けでは、菌１が２つの子を生んだらそれらの菌の番号は２と３、菌２が２つの子を生んだらそれらの菌の番号は４と５になります。

博士は、番号$b$の菌から番号1の菌まで親子関係をさかのぼる順で、菌$b$のすべての祖先を記録することにしました。たとえば、菌5は菌2の子で,菌2は菌1の子なので、菌5の祖先の記録は5,2,1となります。

菌の番号が与えられたとき、その菌のすべての祖先の記録を出力するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$b$

１行に菌の番号$b$ ($1 \leq b \leq 1,000,000$)が与えられる。

出力

菌$b$の祖先の記録を$b$から1まで順番に、１行に番号を１つずつ出力する。

入出力例

入力例１

5

出力例１

5
2
1

入力例２

12

出力例２

12
6
3
1

Note

Algorithm

 

---