콜라츠의 추측(Collatz conjecture) 알고리즘은 다음과 같습니다.

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

어떤 자연수 n이 주어졌을 때, 1부터 시작하여 거꾸로 거슬러 올라가 처음 입력된 자연수 n이 되는 역순의 과정을 출력하는 프로그램을 작성하시오.

입력

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

출력

1부터 시작하여 n에 도달할 때까지의 우박수 경로를 한 줄에 하나씩 역순으로 출력한다.

제한 사항

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

금지 키워드

• for
• while
• goto

예제 입력 1

5

예제 출력 1

1
2
4
8
16
5