문제

콘라츠 추측은 여전히 풀리지 않은 수학 문제를 1937년에 고안한 수학자 로타르 콜라츠의 이름을 딴 추측입니다. 이 문제에 등장하는 수의 묶음은 우박 수열 또는 우박수라 불립니다. (이는 값이 올라갔다 내려갔다 하는 것이 구름의 우박과 비슷하기 때문입니다.) 추측의 내용은 어떤 숫자로 시작을 하든, 결국 수열이 1로 끝난다는 것입니다. 이러한 성질을 동일성이라 부릅니다.

(3n + 1로도 알려진) 계산 과정은 아래와 같습니다.

1. 정수 n이 있습니다.

2. n == 1일 경우: 멈춥니다.

3. n이 짝수일 경우: 수를 2로 나눕니다. 1의 과정으로 돌아갑니다.

4. n이 홀수일 경우: 수를 3으로 곱한 후 1을 더합니다. 1의 과정으로 돌아갑니다.

추측의 내용은, 임의의 양의 정수에 대해 이 과정을 반복할 때 결국 n = 1로 마무리된다는 것입니다. 그동안 등장한 값이 n부터 1까지의 수열을 이룹니다.

예를 들어, n = 14로 출발했다고 가정합시다.

- 14는 짝수이므로 다음 수는 7입니다. (14 / 2)

- 7은 홀수이므로 다음 수는 22입니다. (3 *  7 + 1)

- 22는 짝수이므로 다음 수는 11입니다. (22 / 2)

- 11은 홀수이므로 다음 수는 34입니다. (3 * 11 + 1)

- 34는 짝수이므로 다음 수는 17입니다.

1이 될 때까지 이 과정을 반복하면 나오는 최종 수열은 아래와 같습니다:

14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

당신은 시작점 n이 주어졌을 때, 이 값에 대한 콜라츠 수열을 전부 출력하는 프로그램을 작성해야 합니다.

입력

하나의 정수 n이 주어집니다. n은 1부터 100000 사이 값입니다.

출력

각 원소 사이 하나의 공백을 두고 콜라츠 수열을 출력합니다. 줄의 시작과 끝에는 공백을 추가하지 않습니다.