Given a positive integer $n$, you need to find the lexicographically smallest permutation $p$ of $1 \sim n$ such that the value of $\text{gcd}(1\times p_1, 2\times p_2, \cdots, n \times p_n)$ is maximized.

Where:

• A permutation of $1 \sim n$ is a sequence of length $n$ where each number from $1 \sim n$ appears exactly once.
• $\text{gcd}(x_1, x_2, \cdots, x_n)$ denotes the greatest common divisor of $x_1, x_2, \cdots, x_n$.
• For two permutations $a$ and $b$ of $1 \sim n$, $a$ is lexicographically smaller than $b$ if and only if there exists a positive integer $i$ such that the first $i-1$ elements of $a$ and $b$ are identical, and $a_i < b_i$.

Input

The input consists of a single line containing a positive integer $n$ ($2 \leq n \leq 10^5$).

Output

Output a single line containing $n$ positive integers, representing the permutation $p$ that satisfies the conditions.

Examples

Input 1

2

Output 1

2 1

Input 2

3

Output 2

1 2 3

Note

For the first example:

• When $p=\{1, 2\}$, $\text{gcd}(1\times 1, 2\times 2) = 1$.
• When $p=\{2, 1\}$, $\text{gcd}(1\times 2, 2\times 1) = 2$.

Thus, $\{2, 1\}$ is the permutation $p$ that satisfies the condition.

For the second example:

• When $p=\{1, 2, 3\}$, $\text{gcd}(1\times 1, 2\times 2, 3\times 3) = 1$.
• When $p=\{1, 3, 2\}$, $\text{gcd}(1\times 1, 2\times 3, 3\times 2) = 1$.
• When $p=\{2, 1, 3\}$, $\text{gcd}(1\times 2, 2\times 1, 3\times 3) = 1$.
• When $p=\{2, 3, 1\}$, $\text{gcd}(1\times 2, 2\times 3, 3\times 1) = 1$.
• When $p=\{3, 1, 2\}$, $\text{gcd}(1\times 3, 2\times 1, 3\times 2) = 1$.
• When $p=\{3, 2, 1\}$, $\text{gcd}(1\times 3, 2\times 2, 3\times 1) = 1$.

Thus, $\{1, 2, 3\}$ is the permutation $p$ that satisfies the condition.