Time Limits: 1000 ms Memory Limits: 524288 KB

Description

小X 看到堆成山的数列作业十分头疼，希望聪明的你来帮帮他。考虑数列A=[A1,A2,…,An],定义变换f(A,k)=[A2,A3,.Ak,A1,Ak+2,Ak+3,A2k,Ak+1,…]，也就是把a 分段，每段k 个（最后如果不足k 个，全部分到新的一段里，见样例），然后将每段的第一个移动到该段的最后一个。

现在，小 X想知道 f (f (f (f ([1,2,3,⋯,n],2),3),⋯),n)的结果。

Input

输入一行包含一个整数n 。

Output

输出一行包含n 个整数，表示最终的数列。

Sample Input

1
4

Sample Output

1
2
3
4
5
4 2 3 1
【样例说明】
f ([1,2,3,4],2) = [2,1,4,3]
f ([2,1,4,3],3) = [1,4,2,3]（3单独被分在一组，移动到组的最后一位，仍然是3）
f ([1,4,2,3],4) = [4,2,3,1]

Data Constraint

对于60%的数据，1≤ n ≤10^3。

对于100%的数据，1≤ n ≤10^6。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int a[2*MAXN], n, k;
int main() {
    cin>>n;
    for (int i=1; i<=n; i++) {
        a[i]=i;
    }
    for (int k=2; k<=n; k++) {
        int t=0;
        for (int i=k-1; i<=k+n-2; i+=k) {
            swap (t, a[i]);
        }
        a[k+n-1]=t;
    }
    for (int i=n; i<=2*n-1; i++) {
        cout<<a[i]<<" ";
    }
    return 0;
}