N-Queens

Placing 8 queens on an 8×8 chessboard so that no two of them attack each other is a well-known puzzle. A queen attacks every piece that shares its row, its column, or one of its two diagonals.

A more general version of this problem was posed by Franz Nauck in 1850:

In how many ways can N queens be placed on an N×N board so that no two queens attack each other?

It is known that for every N > 3 at least one such arrangement exists. For example, for N = 26 there are 22317699616364044 arrangements.

Given N, output one valid arrangement of N non-attacking queens on an N×N board. Because a board can admit an enormous number of valid arrangements, you must output the single specific arrangement described in the Output section.

The first line contains a single integer N (4 ≤ N ≤ 100000).

Print N lines. The i-th line must contain a single integer: the column number (from 1 to N) of the queen placed in row i.

Many arrangements are valid, so to make the answer unique you must print the specific arrangement produced by the following construction.

Let E be the list of even numbers 2, 4, 6, … up to N in increasing order, and let O be the list of odd numbers 1, 3, 5, … up to N in increasing order. Adjust the two lists according to the remainder of N divided by 6:

• If N mod 6 = 2: swap the first two elements of O (so O starts with 3, 1, 5, 7, …), then remove the value 5 from O and append it to the end of O.
• If N mod 6 = 3: remove the value 2 from E and append it to the end of E; then remove the values 1 and 3 from O and append them, in that order, to the end of O.
• Otherwise: leave E and O unchanged.

Concatenate E followed by O to obtain a list of N numbers. The i-th number in this list is the column of the queen in row i, which is exactly what you print on line i.