N-Queens Problem

Problem Background

Special for beginners, ^_^

Problem Description

Place $N$ queens on an $N \times N$ chessboard ($N \le 10$) so that they do not attack each other (i.e., no two queens may share the same row, the same column, or the same diagonal). Write a program to find all valid placements.

Input Format

An integer $n$.

Output Format

For each solution, output one line containing the column numbers of the queens in order, separated by spaces. If there is no solution, output no solute!

Sample Input

4

Sample Output

2 4 1 3
3 1 4 2

Constraints

Time limit: 1s, memory limit: 1024KiB for each test case.