Xem xét thuật toán lấy đầu vào là một số nguyên dương ~n~. Nếu ~n~ là chẵn thì thuật toán sẽ chia nó cho 2 (chia lấy số nguyên), nếu ~n~ là lẻ thì thuật toán sẽ nhân nó cho 3 sau đó cộng với 1. Quá trình lặp lại đến khi ~n~ bằng 1. Ví dụ như đối với ~n=3~ thì sẽ như sau: $$ 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 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ị cho trước của ~n~.

Input:

Một dòng nhập vào giá trị của n.

Output:

In ra các giá trị của từng bước thực hiện của thuật toán

Constraints

~1 \leq n \leq 10^6~

Example

Input:

3

Output:

3 10 5 16 8 4 2 1