N-Queen (mod N)

Time limit1sMemory limit512 MB

Summary

Given N, place N queens on an N by N board whose opposite edges are joined, so no two share a row, column, or wrapped diagonal. Print one valid placement, or -1 if none exists.

Level: Medium6 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Given an $N \times N$ chessboard, print one way to place $N$ queens so that no two queens attack each other. The square in row $r$ and column $c$ has coordinates $(r, c)$ . The top-left square is $(1, 1)$ , and the bottom-right square is $(N, N)$ . The opposite edges of the board are joined together. 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$ .

Input

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

Output

If $N$ queens can be placed, print $A_1$ , $A_2$ , $A_3$ , $\cdots$ , $A_N$ on the first line, where $A_i$ is the column number of the queen in row $i$ . ( $1 \le A_i \le N$ )

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

Examples2

Example 1
Input
```
2
```
Expected output
```
-1
```
Example 2
Input
```
5
```
Expected output
```
3 1 4 2 5
```