我们将以下过程称为长度 $$$n$$$ 序列的转换。
如果序列为空,则过程结束。否则,将序列中所有元素的最大公约数 (GCD) 添加到结果中,并从序列中删除一个任意元素。因此,当过程结束时,我们得到了一个 $$$n$$$ 整数序列:每次删除之前序列中所有元素的最大公约数。
给定一个整数序列 $$$1, 2, \dots, n$$$。求其变换的字典顺序最大结果。
如果存在一个索引 $$$i$$$,使得 $$$a_j = b_j$$$ 对于所有 $$$j < i$$$ 和 $$$a_i > b_i$$$。
输入
输入的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1\le n\le 10^6$$$)。
输出
输出 $$$n$$$ 整数 — 按字典顺序排列的最大转换结果。
示例
输入 #1
3
输出 #1
1 1 3
输入 #2
2
输出 #2
1 2
输入 #3
1
输出 #3
1
注意
在第一个示例中,答案可以通过以下方式实现:
- 追加 GCD$$$(1, 2, 3) = 1$$$,删除 $$$2$$$。
- 追加 GCD$$$(1, 3) = 1$$$,删除 $$$1$$$。
- 追加 GCD$$$(3) = 3$$$,删除 $$$3$$$。
我们得到序列 $$$[1, 1, 3]$$$ 作为结果。