Розглянемо алгоритм, який на вході отримує натуральне число ~n~ і, якщо ~n~ парне, алгоритм ділить його на два, а якщо ~n~ непарне, алгоритм множить його на три та додає одиницю.

Алгоритм повторює це, поки ~n~ не стане одиницею.

Наприклад, послідовність для ~n=3~ така:

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

Ваше завдання — змоделювати виконання алгоритму для заданого значення ~n~.

Обмеження

~1 \le n \le 10^6~

Input

Єдиний рядок вводу містить ціле число nn.

Output

Вивести рядок, який містить усі значення ~n~ під час роботи алгоритму.

Sample Input 1

3

Sample Output 1

3 10 5 16 8 4 2 1