题解

题面描述

给定一个整数 $n$（$1\le n\le 10^5$），要求构造一个 $2\times n$ 的矩阵，使得：

• 每一行都是 $[1,n]$ 的一个排列；
• 对于任意两个相邻元素 $a_{i_1,j_1}$ 与 $a_{i_2,j_2}$（满足 $|i_1-i_2|+|j_1-j_2|=1$），都有 $\gcd(a_{i_1,j_1},a_{i_2,j_2})=1$。

题目内容

小红认为一个$2×n$的矩阵如果同时满足:

• 第一行由$[1,n]$的排列构成
• 第二行也由$[1,n]$的排列构成
• 对于任意两个元素 $a_{i_1,j_1}$，$a_{i_2,j_2}$(其中$|i_1-i_2|+|j_1- j_2|= 1$),满足$gcd(a_{i_1,j_1},a_{i_2,j_2})=1$。

则该矩阵是一个好矩阵。 现在给定整数$n$，请你帮助小红构造一个$2×n$的好矩阵，可以证明始终存在一个满足条件的解。

长度为 $n$ 的排列是由$1$~$n$这$n$个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{$2,3, 1,5,4$} 是一个长度为$5$的排列，而{$1, 2,2$} 和 {$1,3,4$}都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述

一个整数n(1≤n≤10^5)，表示矩阵的列长。

输出描述

共$2$行$n$列，同一行的元素以空格隔开，若存在多解，输出任意一个满足条件的即可。

样例1

输入

2

输出

2 1
1 2