Problem D
Collatz Conjecture

Let $a$ be a positive integer and consider the sequence where $x_0 = a$ and

The Collatz conjecture states that this sequence will always reach $1$.

For example, if $a = 10$, then $x_0 = 10, x_1 = 5, x_2 = 16, x_3 = 8, x_4 = 4, x_5 = 2$ and $x_6 = 1$.

Write a program that reads a positive integer from the user and, using a while loop, outputs each element of the above sequence until it reaches $1$.

Input

Input consists of one line with one integer $x_0$, the initial term of the sequence, where $0 \leq x_0 \leq 100\, 000$.

Output

Output consists of one or more lines, where the $i$th line contains the integer $x_i$, for $i \geq 0$.

2

2
1

3

3
10
5
16
8
4
2
1

19

19
58
29
88
44
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

25

25
76
38
19
58
29
88
44
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1