题目描述

棋盘表演需要在 $n\times n$ 的棋盘上摆放 $n$ 个女王。每一行、每一列必须恰好有一个女王，并且任意两个女王不能位于同一条对角线上。

一个方案用 $n$ 个整数表示，第 $i$ 个整数表示第 $i$ 行女王所在的列。请按照字典序输出最前面的三个方案；若方案不足三个，则输出全部方案。最后再输出方案总数。

输入格式

第一行包含一个整数 $n$。

输出格式

先输出最多三个方案，每个方案占一行，列号之间用一个空格分隔；最后一行输出方案总数。

4

2 4 1 3
3 1 4 2
2

数据范围与提示

• $1\le n\le 13$