Xét thuật toán sau nhận đầu vào là một số nguyên dương n. Nếu n chẵn, thuật toán sẽ chia nó cho hai, và nếu n lẻ, thuật toán nhân ba nó lên rồi cộng thêm một đơn vị. Thuật toán trên lặp lại điều này cho tới khi n bằng 1. Ví dụ, dãy số thực hiện với n = 3 là:

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

Việc của bạn là hãy mô phỏng lại cách hoạt động của thuật toán với một giá trị n cho trước.

Input

Một dòng duy nhất chứa số n. (1 ≤ n ≤ 10^6)

Output

In ra một dòng lần lượt chứa từng giá trị của n trong khi chạy thuật toán.

Ví dụ

Input

3

Output

3 10 5 16 8 4 2 1