Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

Consider the following algorithm, which generates a (not necessarily uniformly) random permutation of numbers $1$ through $N$:

P := [1, 2, ..., N]
for i in 1..N do
j := rand(1, N)
swap(P[i], P[j])

Here, rand(1, N) returns a uniformly random integer between $1$ and $N$ inclusive. Let's denote the probability that the permutation generated by this algorithm is $P$ by $p(P)$.

Find a permutation $P_{1}$ such that $p(P_{1})$ is maximum possible and a permutation $P_{2}$ such that $p(P_{2})$ is minimum possible.

------ Input ------
The first and only line of the input contains a single integer $N$.

------ Output ------
Print two lines. The first line should contain $N$ space-separated integers denoting your permutation $P_{1}$. The second line should contain $N$ space-separated integers denoting your permutation $P_{2}$.

If there are multiple answers, you may print any one.

------ Constraints ------
$1 ≤ N ≤ 17$

------ Subtasks ------
Subtask #1 (20 points): $1 ≤ N ≤ 7$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------
2
----- Sample Output 1 ------
1 2
2 1
----- explanation 1 ------
There are two possible permutations, $[1, 2]$ and $[2, 1]$. Both are equally likely to appear as the result of the given algorithm, so any pair of permutations is a valid answer.

见题面

见题面