John Doe 找到了美丽的排列公式。
让我们进行排列 p = p1, p2, ..., pn。让我们定义这个排列的变换 f:
$$f(p,k) = \overbrace{p_{2}, p_{3}, \ldots, p_{k}, p_{1}, p_{k+2}, p_{k+3}, \ldots, p_{n}, p_{rk+1}}^{r}$$
其中 k (k > 1) 是整数,变换参数 r 是 rk ≤ n 的最大整数。如果 rk = n,则省略元素 prk + 1、prk + 2 等。换句话说,所描述的置换p的变换将长度为k的每个连续块以及长度等于n除以k之后的余数的最后一个块循环地向左移位。
John Doe 认为排列 f(f( ... f(p = [1, 2, ..., n], 2) ... , n - 1), n) 很漂亮。不幸的是,他无法快速找到他感兴趣的美丽排列。这就是他请你帮助他的原因。
你的任务是为给定的 n 找到一个漂亮的排列。有关说明,请参阅第三个示例的注释。
输入
单行包含整数 n (2 ≤ n ≤ 106)。
输出
打印 n 个不同的空格分隔整数(从 1 到 n)——一个大小为 n 的漂亮排列。
示例
输入 #1
2
输出 #1
2 1
输入 #2
3
输出 #2
1 3 2
输入 #3
4
输出 #3
4 2 3 1
注意
第三个测试样本的注释:
- f([1, 2, 3, 4], 2) = [2, 1, 4, 3]
- f([2, 1, 4, 3], 3) = [1, 4, 2, 3]
- f([1, 4, 2, 3], 4) = [4, 2, 3, 1]