题目描述

要在 N×N（N≤8）的国际象棋棋盘中放 N 个皇后，使得任意两个皇后都不能互相吃（提示：皇后能吃同一行、同一列、同一对角线的其他皇后）。 请问有多少种方案，并按字典序输出所有的方案。每种方案输出每一行皇后的纵坐标（场宽为 5），如果无解，则输出“no solute!”。

输入格式

一行一个整数 N。

输出格式

每行对应一种方案，具体格式参见输出样例。

样例数据

input

4

output

2 4 1 3
3 1 4 2

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$