Collatz Sequence Generation

Given a positive integer \(S\) that satisfies \(1 \le S \le 10^6\), generate the Collatz sequence (also known as the 3n+1 sequence) starting from \(S\). The sequence is defined by the following rules:

• If \(S\) is even, then the next number is \(\frac{S}{2}\).
• If \(S\) is odd, then the next number is \(3S+1\).

The process is repeated until the number 1 is reached. It is guaranteed that for any \(S\) in the given range, the sequence will eventually reach 1.

Example: For \(S = 6\), the sequence is: 6, 3, 10, 5, 16, 8, 4, 2, 1.

inputFormat

The input consists of a single integer (S) (1 (\le S \le 10^6)) provided via standard input.

outputFormat

Output the Collatz sequence starting from (S) as a sequence of space-separated integers on a single line. The sequence must always end with the integer 1.## sample

6

6 3 10 5 16 8 4 2 1