Weird Algorithm

Weird Algorithm

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

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

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

Input

The only input line contains an integer nn.

Output

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

Constraints

• 1≤n≤1061≤n≤106

Example

Input:
3

Output:
3 10 5 16 8 4 2 1