Before giving you presents, Santa challenges you to a game of cards. You and Santa are both given $N$ cards, labelled from $1$ to $N$.

Upon receiving the cards, you and Santa may both reorder the cards however you wish. After reordering the cards, you both lay your cards down from left to right. The total festivity of an arrangement of cards is equal to the number of subarrays where the maximum element is equal to the subarray's size. The player whose hand has the highest festivity is declared the winner. If two arrangements have the same festivity, the one that is lexicographically larger is considered to be superior. Given $N$, your job is to output a hand for both you and Santa such that you win by the largest margin. In other words, output the best and worst possible hands for the game.

Definition: An array $A$ is lexicographically larger than an array $B$ if $A\ne B$ and at the first index $i$ where $A_i\ne B_i$, $A_i>B_i$.

Constraints

$1\le N\le {10}^6$

Subtask 1 [10%]

$1\le N\le 2$

Subtask 2 [20%]

$1\le N\le 8$

Subtask 3 [70%]

No additional constraints.

Input Specification

The first and only line contains a single integer, $N$.

Output Specification

On the first line, output $N$ space-separated integers, the best possible card arrangement for the game.

On the second line, output $N$ space-separated integers, the worst possible card arrangement for the game.

Sample Input

3

Sample Output

3 2 1
1 3 2

Explanation of Sample

Here, the largest festivity possible is 3, and the smallest festivity possible is 2. Note that the output matches the lexicographical specifications provided.