Xét một thuật toán với đầu vào là một số nguyên dương \(n\). Nếu \(n\) là số chẵn, thuật toán chia \(n\) cho hai; nếu \(n\) là số lẻ, thuật toán nhân \(n\) với ba và cộng thêm một. Thuật toán lặp lại quá trình này cho đến khi \(n\) trở thành một.

Ví dụ, với \(n = 3\), dãy số là:

\(3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\)

Nhiệm vụ của bạn là mô phỏng quá trình thực hiện thuật toán này với một giá trị \(n\) cho trước.

Input

Dòng duy nhất chứa một số nguyên \(n (1 \leq n \leq 10^6)\)

Output

In ra một dòng chứa tất cả các giá trị của \(n\) trong quá trình thực hiện thuật toán.

Ví dụ

Dữ liệu vào:

3

Kết quả ra:

3 10 5 16 8 4 2 1