The Collatz Conjecture is one of the most famous unsolved mathematical problems.

Given an integer \(N\), consider the following algorithm:

• If \(N\) is even, divide it by \(2\).
• If \(N\) is odd, multiply it by \(3\) then add \(1\).

The Collatz Conjecture states that for any positive integer \(N\), repeatedly following this algorithm will make it eventually become \(1\).

Computer programs have proven that the Collatz Conjecture holds up to \(2.4 \times 10^{21}\).

Your task is to write a program that can help us to validate that an integer \(N\) follows the Collatz Conjecture: given the integer \(N\), simulate the Collatz Conjecture.
Make sure to print the numbers on the same line!

Input Specification

The first line will contain the integer \(N\) (\(1 \le N \le 10^6\)).

Output Specification

Print the sequence of values \(N\).

Sample Input

5

Sample Output

5 16 8 4 2 1