题目描述

给定一个正整数 $n$。你需要找到，在所有使得 $\text{gcd}(1\times p_1,2\times p_2,\cdots,n \times p_n)$ 的值尽可能大的 $1\sim n$ 的排列 $p$ 中，字典序最小的排列 $p$。

其中：

• $1 \sim n$ 的排列表示长度为 $n$ 且 $1\sim n$ 均恰好出现一次的序列；
• $\text{gcd}(x_1,x_2,\cdots,x_n)$ 表示 $x_1,x_2,\cdots,x_n$ 的最大公因数；
• 对于两个 $1\sim n$ 的排列 $a,b$，$a$ 的字典序比 $b$ 小，当且仅当存在一个正整数 $i$，满足 $a$ 的前 $i-1$ 项与 $b$ 的前 $i-1$ 项均相同且 $a_i \lt b_i$。

输入格式

输入一行，包含一个正整数 $n$。

输出格式

输出一行，包含 $n$ 个正整数，表示满足条件的 $1\sim n$ 的排列 $p$。

2

2 1

3

1 2 3

提示

样例解释 #1

• 当 $p=\{1,2\}$ 时，$\text{gcd}(1\times1,2\times2)=1$；
• 当 $p=\{2,1\}$ 时，$\text{gcd}(1\times2,2\times1)=2$；

所以 $\{2,1\}$ 为满足条件的排列 $p$。

样例解释 #2

• 当 $p=\{1,2,3\}$ 时，$\text{gcd}(1\times1,2\times2,3\times3)=1$；
• 当 $p=\{1,3,2\}$ 时，$\text{gcd}(1\times1,2\times3,3\times2)=1$；
• 当 $p=\{2,1,3\}$ 时，$\text{gcd}(1\times2,2\times1,3\times3)=1$；
• 当 $p=\{2,3,1\}$ 时，$\text{gcd}(1\times2,2\times3,3\times1)=1$；
• 当 $p=\{3,1,2\}$ 时，$\text{gcd}(1\times3,2\times1,3\times2)=1$；
• 当 $p=\{3,2,1\}$ 时，$\text{gcd}(1\times3,2\times2,3\times1)=1$；

所以 $\{1,2,3\}$ 为满足条件的排列 $p$。

数据范围

对于所有测试数据，$2 \le n \le 10^5$。