Thuật toán kỳ lạ (Weird Algorithm)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Bắt đầu với số nguyên dương $n$. In giá trị ban đầu, rồi lặp lại quy tắc: nếu số hiện tại chẵn thì chia cho 2; nếu lẻ thì nhân 3 cộng 1. In mọi giá trị mới, dừng ngay khi bằng 1; giữ nguyên thứ tự từ n đến 1, các số cách nhau một khoảng trắng.

Input

Một số nguyên dương $n$.

Output

Một dòng gồm toàn bộ dãy giá trị từ $n$ đến 1, cách nhau bởi dấu cách.

Subtask

• Subtask 1 (20%): $1\le n\le10$.
• Subtask 2 (30%): $1\le n\le1000$.
• Subtask 3 (50%): $1\le n\le10^6$.

Ví dụ

Ví dụ 1

Input

3

Output

3 10 5 16 8 4 2 1

Giải thích

Bắt đầu 3 lẻ→10; 10 chẵn→5; 5 lẻ→16; tiếp tục 8,4,2,1 rồi dừng. Phải in cả 3 lẫn 1.

Ví dụ 2

Input

1

Output

1

Giải thích

Đầu vào đã là 1; không tính thêm bước nhưng vẫn in giá trị ban đầu.