Розглянемо алгоритм, який на входi отримує натуральне число \(n\) i, якщо \(n\) парне, алгоритм дiлить його на два, а якщо \(n\) непарне, алгоритм множить його на три та додає одиницю. Алгоритм повторює це, поки \(n\) не стане одиницею. Наприклад, послiдовнiсть для \(n = 3\) така:

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

Ваше завдання - змоделювати виконання алгоритму для заданого значення \(n\).

Обмеження: \( 1 \le n \le 10^6 \)

Формат вхiдних даних

Єдиний рядок вводу мiстить цiле число \(n\).

Формат вихiдних даних

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

Приклад вхідних даних:

3

Приклад виходових даних:

3 10 5 16 8 4 2 1