题目描述

在 $N\times N$ 棋盘中放置 $N$ 个皇后，使任意两个皇后不在同一行、同一列或同一对角线上。按字典序输出所有方案。

输入格式

一行正整数 $N$。

输出格式

每行输出一个方案：依次给出各行皇后的列编号，从1开始。各数用空格分开。没有方案时输出 no solute!。

样例

4

2 4 1 3
3 1 4 2

数据范围

$1\le N\le8$。