Weird Algorithm

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Start from positive n and print it. While the current value is not one, divide by two if even, or multiply by three and add one if odd; print every new value, ending at one, in order.

Input

One positive integer n.

Output

Print the entire sequence from n through 1, separated by spaces.

Subtasks

• Subtask 1 (20%): $1\le n\le10$.
• Subtask 2 (30%): $1\le n\le1000$.
• Subtask 3 (50%): $1\le n\le10^6$.

Examples

Example 1

Input

3

Output

3 10 5 16 8 4 2 1

Explanation

Start at 3, then obtain 10,5,16,8,4,2,1; include both endpoints.

Example 2

Input

1

Output

1

Explanation

The starting value is already one and must still be printed.