题目描述

在$\red{n×n}$格的棋盘上放置彼此不受攻击的$\red{n}$个皇后。

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

$\red{n}$后问题等价于再$\red{n×n}$的棋盘上放置$\red{n}$个皇后，任何$\red{2}$个皇后不妨在同一行或同一列或同一斜线上。

输入格式

给定棋盘的大小$\red{n}$ ($\red{n ≤ 13}$)

输出格式

输出每一种方案所占的列号，列号小的先输出。每个整数占5位输出(右对齐）,如果没有结果输出"no solute!"。

样例

输入样例

4

输出样例

2    4    1    3
3    1    4    2

数据范围与提示

$\red{n ≤ 13}$