C. Преобразование последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем преобразованием последовательности из $$$n$$$ элементов следующий процесс:

Если последовательность пуста, то процесс завершается. Иначе допишем к ответу наибольший общий делитель (НОД) всех элементов последовательности, удалим один любой элемент последовательности и продолжим процесс. В результате на бумаге получится последовательность из $$$n$$$ чисел — наибольшие общие делители всех чисел последовательности перед каждым удалением.

Изначально дана последовательность целых чисел $$$1, 2, \dots, n$$$. Найдите лексикографически максимальный результат преобразования этой последовательности.

Последовательность $$$a_1, a_2, \ldots, a_n$$$ лексикографически больше последовательности $$$b_1, b_2, \ldots, b_n$$$, если существует такой индекс $$$i$$$, что $$$a_j = b_j$$$ для всех $$$j < i$$$, и при этом $$$a_i > b_i$$$.

Входные данные

В первой и единственной строке входных данных дано одно целое число $$$n$$$ ($$$1\le n\le 10^6$$$).

Выходные данные

Выведите $$$n$$$ целых чисел — лексикографически максимальный результат преобразования.

Примеры
Входные данные
3
Выходные данные
1 1 3 
Входные данные
2
Выходные данные
1 2 
Входные данные
1
Выходные данные
1 
Примечание

В первом примере результат достигается так:

  • Запишем НОД$$$(1, 2, 3) = 1$$$ и удалим $$$2$$$.
  • Запишем НОД$$$(1, 3) = 1$$$ и удалим $$$1$$$.
  • Запишем НОД$$$(3) = 3$$$ и удалим $$$3$$$.

В результате преобразования будет написана последовательность $$$[1, 1, 3]$$$.