Cho một số nguyên dương n. Người ta thực hiện biến đổi số n theo cách như sau: Nếu n chẵn, ta chia nó cho hai và nếu n lẻ, ta nhân nó với ba và cộng một. Thuật toán lặp lại, cho đến khi n = 1.

Ví dụ, trình tự cho n = 3 như sau: 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Yêu cầu: Em hãy lập trình mô phỏng việc thực hiện thuật toán trên.

Input:

Gồm một dòng duy nhất chứa số nguyên n.

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 biến đổi, các giá trị cách nhau bởi một dấu cách.

Giới hạn: 1 ≤ n ≤ 10⁶

Ví dụ: