30911번 - 🧩 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$개를 서로 공격할 수 없게 놓는 특별한 방법 한 가지를 출력해 보자.

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

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

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