该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

出一个正整数 n，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 3 再加 1，否则除以 2。经过若干次循环后，最终都会回到 1。经过验证很大的数字都可以按照这样的方式比变成 1，所以被称为“冰雹猜想”。例如当n 是 20，变化的过程是 20→10→5→16→8→4→2→1。 根据给定的数字，验证这个猜想。

Format

Input

输入一个正整数 n（1 ≤ n ≤ 1 000 000）

Output

输出若干行，每行一个数字，表示变化过程，

Samples

20

20
10
5
16
8
4
2
1

Limitation

1s, 1024KiB for each test case.