Thuật toán kỳ lạ

Trong một buổi tập bơi, FullHouse Dev được huấn luyện viên giao cho một bài toán thú vị để rèn luyện tư duy logic. Họ phải mô phỏng một thuật toán đặc biệt, giống như cách họ phải điều chỉnh nhịp thở và động tác khi bơi. Với tinh thần nhiệt huyết, FullHouse Dev đã bắt đầu giải quyết bài toán này.

Bài toán

Xét một thuật toán nhận vào một số nguyên dương \(n\). Nếu \(n\) chẵn, thuật toán chia nó cho hai, và nếu \(n\) 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\) bằng một. Ví dụ, chuỗi cho \(n = 3\) như sau: \[ 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\] Nhiệm vụ của FullHouse Dev là mô phỏng việc thực thi thuật toán này cho một giá trị \(n\) cho trước.

INPUT FORMAT:

• Dòng duy nhất chứa một số nguyên \(n\).

OUTPUT FORMAT:

• 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.

Ràng buộc:

• \(1 \leq n \leq 10^6\)

Ví dụ

INPUT

3

OUTPUT

3 10 5 16 8 4 2 1

Giải thích

Với \(n = 3\), thuật toán thực hiện các bước sau:

1. \(3\) là số lẻ, nên \(3 * 3 + 1 = 10\)
2. \(10\) là số chẵn, nên \(10 / 2 = 5\)
3. \(5\) là số lẻ, nên \(5 * 3 + 1 = 16\)
4. \(16\) là số chẵn, nên \(16 / 2 = 8\)
5. \(8\) là số chẵn, nên \(8 / 2 = 4\)
6. \(4\) là số chẵn, nên \(4 / 2 = 2\)
7. \(2\) là số chẵn, nên \(2 / 2 = 1\)
8. Thuật toán kết thúc khi \(n = 1\)

Vì vậy, chuỗi kết quả là 3 10 5 16 8 4 2 1.