NL-Queen (mod N)

$N \times N$ 체스판이 주어질 때, 체스판에 퀸 $N$개를 서로 공격할 수 없게 놓는 특별한 방법 한 가지를 출력해 보자. 체스판의 $r$행 $c$열 좌표는 $(r, c)$이며, 가장 왼쪽 위 칸은 $(1, 1)$, 가장 오른쪽 아래 칸은 $(N, N)$이다. 체스판의 평행한 변끼리 연결되어 있어, 두 퀸의 좌표가 각각 $(a, b)$, $(c, d)$일 때 다음 네 조건 중 적어도 하나를 만족하면 두 퀸은 서로 공격하는 상태이다.

1. $a = c$
2. $b = d$
3. $a+b \equiv c+d \pmod N$
4. $a-b \equiv c-d \pmod N$

퀸 $N$개가 서로 공격하지 않는 배치에서 $i$번째 행에 있는 퀸의 열 번호를 $A_i$라 하자. 정수 $k$가 모든 $i$에 대해 $A_{(i \bmod N) + 1} - A_i \equiv k \pmod N$을 만족하면 이 배치는 $k$-선형이라고 한다. 모든 정수 $k$에 대해 $k$-선형이 아니면 이 배치를 특별하다고 한다.

첫 번째 줄에 정수 $N$이 주어진다. ($2 \le N \le 500\,000$)

$N$개의 퀸을 놓을 수 있다면, 첫 번째 줄에 $A_1, A_2, A_3, \cdots, A_N$을 출력한다. ($1 \le A_i \le N$)

$N$개의 퀸을 놓을 수 없다면 -1을 출력한다.