CSES - Thuật toán Kỳ lạ (Weird Algorithm)

Giới hạn thời gian: 1.00 s
Giới hạn bộ nhớ: 512 MB

Xét một thuật toán nhận vào 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 rồi cộng thêm một.

Thuật toán lặp lại quá trình trên cho đến khi n trở thành 1.

Ví dụ, dãy giá trị với n = 3 sẽ là:

~3 → 10 → 5 → 16 → 8 → 4 → 2 → 1~

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

Input

Dòng duy nhất của đầu vào chứa một số nguyên n.

Output

In ra một dòng chứa toàn bộ các giá trị của n trong quá trình thuật toán chạy.

Ràng buộc

~1 ≤ n ≤ 10^6~

Ví dụ

Input:

3

Output:

3 10 5 16 8 4 2 1