콜라츠의 추측(Collatz conjecture) 혹은 우박수 문제라고 불리는 이 알고리즘은 다음과 같습니다.

1. 어떤 자연수 n이 입력된다.
2. n이 홀수이면 3n + 1을 한다.
3. n이 짝수이면 n / 2를 한다.
4. n이 1이 될 때까지 2번과 3번 과정을 반복한다.

어떤 자연수 n이 주어졌을 때, 위 알고리즘에 의해 1이 되는 과정의 모든 수를 순서대로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n이 입력된다.

출력

n이 1이 될 때까지 거치는 과정을 한 줄에 하나씩 순서대로 출력한다.

제한 사항

• 1 ≤ n ≤ 10,000,000
• 3n + 1이 되는 과정에서 32비트 정수(int) 범위를 넘는 수는 입력으로 주어지지 않는다.

금지 키워드

• for
• while
• goto

예제 입력 1

5

예제 출력 1

5
16
8
4
2
1