34518번 - Double Permutation 스페셜 저지

양의 정수 $N$이 주어진다. 다음 조건을 만족하는 $2$행 $N$열의 격자를 구해보자.

• 각 칸에는 $1$ 이상 $N$ 이하의 정수 중 하나를 쓴다.
• $1$ 이상 $N$ 이하의 모든 정수는 격자 전체에서 정확히 2번씩 등장해야 한다.
• 모든 정수 $x$에 대하여, 해당 숫자가 적힌 두 칸의 맨해튼 거리^[1]가 정확히 $x$가 되어야 한다. $(1 \le x \le N)$

첫 번째 줄에 정수 $N$이 주어진다.

만약 조건을 만족하는 격자가 있다면 다음 $2$개의 줄에 걸쳐 각 줄에 $N$개의 정수를 공백으로 구분하여 출력한다. $i$번째 줄의 $j$번째 정수는 격자의 $i$행 $j$열에 적을 정수를 의미한다. 가능한 격자가 여러 개라면 그중 아무것이나 출력한다. $(1 \le i \le 2$; $1 \le j \le N)$

만약 조건을 만족하는 격자가 없다면 첫 번째 줄에 -1을 출력한다.

• $1 \le N \le 5\,000$

[1] 격자의 $a$행 $b$열과 $c$행 $d$열의 맨해튼 거리는 $|a - c| + |b - d|$이다.