NL-Queen (mod N)

Given an $N \times N$ chessboard, print one special way to place $N$ queens so that no two queens attack each other. The square in row $r$ and column $c$ is $(r, c)$. The top-left square is $(1, 1)$ and the bottom-right square is $(N, N)$. Opposite edges of the board are connected, so the board wraps around. Two queens at $(a, b)$ and $(c, d)$ attack each other if at least one of the following four conditions holds.

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

In a placement where no two queens attack each other, let $A_i$ be the column of the queen in row $i$. If an integer $k$ satisfies $A_{(i \bmod N) + 1} - A_i \equiv k \pmod N$ for every $i$, the placement is called $k$-linear. If the placement is not $k$-linear for any integer $k$, it is called special.

The first line contains an integer $N$. ($2 \le N \le 500\,000$)

If $N$ queens can be placed, print $A_1, A_2, A_3, \cdots, A_N$ on the first line. ($1 \le A_i \le N$)

If $N$ queens cannot be placed, print -1.