← 返回题目列表

Codeforces · 286/B

B. 换档

中文机器翻译题面 查看原题

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]