在$N \times N$的棋盘上放置$N$个皇后（$n \leq 10$）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置$2$个皇后），编程求解所有的摆放方法。

输入格式

$n$

输出格式

每行输出一种方案，每种方案顺序输出皇后所在的列号，各个数之间有空格隔开。若无方案，则输出no solute!

样例

样例输入

4

样例输出

2  4  1  3
3  1  4  2

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$512000\mathrm{KB}$