Description

Consider an algorithm that takes as input a positive integer n. If n is even, thealgorithm divides it by two, and if m is odd, the algorithm multiplies it by threeand adds one. The algorithm repeats this, until m is one. For example, thesequence for n = 3 is as follows:

3→10→5→16→8→4→2→1

Your task is to simulate the execution of the algorithm for a given value of n.

Format

Input

The only input line contains an integer n.

Output

Print a line that contains all values of n during the algorithm.

Samples

3

3 10 5 16 8 4 2 1

Limitation

• 1 ≤ n ≤ 10^6
• Time limit: 1.00 s
• Memory limit: 512 MB