N-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$이 주어진다. ($1 \le N \le 500\,000$)

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

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