题目描述

在一个 $n \times n$ 的棋盘上放置 $n$ 个棋子，使得每行、每列有且只有一个棋子，且每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

一种合法的放置方案可以用一个长度为 $n$ 的序列表示，第 $i$ 个数字表示第 $i$ 行棋子所在的列号。

请找出所有合法的放置方案，按字典序输出前 $3$ 个解，并在最后一行输出解的总数。

输入格式

一行一个正整数 $n$，表示棋盘大小。

输出格式

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

样例

6

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$。

使用回溯法（DFS）依次在每一行尝试放置，用数组记录列、主对角线、副对角线的占用情况即可高效剪枝。