题目描述

《n皇后》

【n皇后】 【 八皇后 Checker Challenge】 会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。 如何将n个皇后放在棋盘上（有n * n个方格），使它们谁也不能被吃掉！这就是著名的N皇后问题。 请试着在nxn的国际象棋棋盘上放置n个皇后使得她们互不攻击。求方案总数，并输出前3种放法。

输入格式

一个数字N (6<=N<=14) 表示棋盘是N x N大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

样例

输入样例 1

7

输出样例 1

1 3 5 7 2 4 6
1 4 7 3 6 2 5
1 5 2 6 3 7 4
40

输入样例 2

8

输出样例 2

1 5 8 6 3 7 2 4
1 6 8 3 7 4 2 5
1 7 4 6 8 2 5 3
92