N 皇后挑战

题目描述

Y 同学正在研究一个经典的棋盘问题。

给定一个大小为 $N \times N$ 的网格棋盘，Y 同学需要在该棋盘上放置 $N$ 个棋子。放置棋子时必须严格满足以下限制条件：

1. 棋盘上的每一行有且仅有一个棋子；
2. 棋盘上的每一列有且仅有一个棋子；
3. 棋盘上的任意一条斜线（包含从左上到右下方向、从右上到左下方向的所有平行斜线）上至多只能有一个棋子。

由于每一行恰好有一个棋子，一种合法的放置方案可以唯一地用一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$ 来表示，其中 $A_i$ 表示放置在第 $i$ 行的棋子所在的列编号（$1 \le A_i \le N$）。

请你编写程序帮助 Y 同学找出所有可能的合法放置方案，并将这些方案对应的序列 $A$ 按照字典序进行升序排列。你需要输出字典序最小的前 $3$ 种方案，最后再输出合法方案的总数。

输入格式

输入仅包含一行，为一个正整数 $N$，表示棋盘的大小以及需要放置的棋子数量。

输出格式

输出共四行。

前三行分别输出字典序排在前 $3$ 位的合法方案对应的序列。每行包含 $N$ 个正整数，相邻两个整数之间由一个空格隔开。

第四行输出一个正整数，表示满足所有限制条件的放置方案总数。

样例

样例输入 #1

6

样例输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

数据范围与约定

对于 $100\%$ 的数据，保证 $6 \le N \le 13$。