题目内容

给定一个正整数 $n$，请构造一个 $2 \times n$ 的矩阵 $A$，满足下述条件：

• 第一行是 $1$ 到 $n$ 的一个排列，第二行也是 $1$ 到 $n$ 的一个排列。排列是指由 $1$ 至 $n$ 的所有整数以任意顺序组成的序列，每个数恰好出现一次。
• 对于矩阵中任意两个在网格上相邻的元素（即它们的曼哈顿距离 $|i_1-i_2|+|j_1-j_2| = 1$），都有 $\gcd(A_{i_1,j_1}, A_{i_2,j_2}) = 1$。

可以证明，对于任意 $n$，满足条件的矩阵总是存在的。你只需输出任意一个合法方案。

整数 $n$ 的范围为 $1 \le n \le 10^5$。

输入描述

输入仅一行，包含一个整数 $n$。

输出描述

输出共两行，每行包含 $n$ 个用空格分隔的整数，分别表示矩阵的第一行与第二行。

样例1

输入

1

输出

1
1

说明

当 $n=1$ 时，矩阵只有一列，两个元素均为 1。此时只有一对垂直相邻的元素，$\gcd(1,1)=1$，满足条件。

样例2

输入

3

输出

1 2 3
2 3 1

说明

第一行是 1 到 3 的顺序排列，第二行是 2, 3, 1。

水平方向：第一行相邻对 $(1,2)$ 和 $(2,3)$ 的 $\gcd$ 均为 1；第二行相邻对 $(2,3)$ 和 $(3,1)$ 的 $\gcd$ 也均为 1。 垂直方向：同一列的三对 $(1,2)$、$(2,3)$、$(3,1)$ 的 $\gcd$ 也均为 1。所有相邻数均互质，符合要求。

样例3

输入

5

输出

1 2 3 4 5
2 3 4 5 1

说明

第一行依次为 1, 2, 3, 4, 5，第二行依次为 2, 3, 4, 5, 1。

根据连续整数互质的性质，水平相邻（如 1 与 2、4 与 5）和垂直相邻（如 1 与 2、5 与 1）的最大公约数均为 1。因此该构造满足题目要求。