F. Lama Pute Pute
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kantipa wants to coordinate a dance performance where the dancers sit while dancing. The dance consists of $$$N$$$ dancers sitting in a single row. The stage consists of $$$10^{100}$$$ pre-made slots for the dancers to sit, numbered from $$$1$$$ to $$$10^{100}$$$ from left to right. These slots are equally spaced.

A configuration of the $$$N$$$ dancers is valid if and only if all of the following are satisfied:

  • The dancers sit on different slots.
  • There exists an integer $$$k$$$ such that for any pair of two dancers with no other dancers between them, the distance between the two is $$$k$$$. Such valid configuration is said to be $$$k$$$-separated.

There are $$$N$$$ dancers numbered from $$$1$$$ to $$$N$$$. Initially, all $$$N$$$ dancers are sitting on different slots among slots $$$1$$$ through $$$N$$$. In other words, there exists an array $$$P$$$ that's a permutation of $$$[1,2,\ldots,N]$$$ such that dancer $$$i$$$ is initially sitting on slot $$$P_i$$$.

For a permutation $$$P$$$, Kantipa defines the value of $$$f(x)$$$ ($$$0\leq x\leq N-2$$$) as the number of different values of $$$\mathbf{k}$$$ such that Kantipa can rearrange the positions of dancers $$$1$$$ through $$$x$$$ to any slots to make the configuration $$$k$$$-separated, while not changing the positions of dancers $$$x+1$$$ through $$$N$$$.

Find any permutation $$$P$$$ such that the value of $$$f(0)+f(1)+f(2)+\ldots+f(N-2)$$$ is as big as possible! If there are multiple solutions, output any of them.

Input

The only line contains a single integer $$$N$$$ ($$$2 \leq N \leq 300\,000$$$) — the number of dancers.

Output

Print $$$N$$$ integers in one line. The $$$i$$$-th integer is the value of $$$P_i$$$ (the initial position of dancer $$$i$$$). If there are multiple solutions, output any of them.

Example
Input
5
Output
4 2 3 5 1
Note

For $$$f(0)$$$, we can only do nothing, which would make it $$$1$$$-separated, so $$$f(0)=1$$$.

For $$$f(1)$$$, by being able to rearrange the position of dancer $$$1$$$, we can still only make it $$$1$$$-separated, so $$$f(1)=1$$$.

For $$$f(2)$$$, by being able to rearrange the positions of dancers $$$1$$$ and $$$2$$$, not only can we make it $$$1$$$-separated, we can also make it $$$2$$$-separated by moving dancer $$$1$$$ to slot $$$9$$$ and moving dancer $$$2$$$ to slot $$$7$$$, so $$$f(2)=2$$$.

For $$$f(3)$$$, by being able to rearrange the positions of dancers $$$1$$$, $$$2$$$, and $$$3$$$, not only can we make it $$$1$$$-separated and $$$2$$$-separated, we can also make it $$$4$$$-separated by moving dancer $$$1$$$ to slot $$$9$$$, moving dancer $$$2$$$ to slot $$$17$$$, and moving dancer $$$3$$$ to slot $$$13$$$, so $$$f(2)=3$$$.

Therefore, $$$f(0)+f(1)+f(2)+f(3)=7$$$, which is the biggest possible value of this sum for $$$5$$$ dancers.