昆仑秘境・星纹玉玦的千年谜题

小哥张起灵为了夺回在长生赛季后失去的一切，发现了关于 “无相棋盘” 的惊天秘密：这块 n×n的上古棋盘，镶嵌着 n枚星纹玉玦 —— 它们是伏羲氏为镇压九州地脉异动而设的法器。唯有遵循以下神谕般的规则摆放，才能平息地脉，否则将引发山崩海啸：

每一行、每一列必须且仅能镶嵌一枚玉玦；

任何两枚玉玦不得落于同一条 “元素对角线” 上（包括所有与主对角线或副对角线平行的对角线，否则将触发金、木、水、火、土元素对冲，酿就灭顶之灾）。

古籍中记载，正确的摆放可通过 “行 - 列序列” 传世：第 i个数字代表第 i行玉玦的列位。例如

n=6时，一段被验证的有效序列是 2 4 6 1 3 5（即第 1 行列 2、第 2 行列 4…… 第 6 行列 5）。

帮助小哥找出所有符合神谕的摆放方式，按字典序输出前 3 种序列，并统计总数 —— 这是打开昆仑墟最终密室、阻止地脉暴走的唯一钥匙。

输入格式：

一行一个正整数 n，表示无相棋盘的规模为 n×n。

输出格式：

前 3 行：依次输出前 3 个符合神谕的行 - 列序列，数字间以空格分隔； 第 4 行：一个整数，表示所有有效摆放方式的总数。

输入输出样例

输入 ：

6

输出 ：

2 4 6 1 3 5

3 6 2 5 1 4

4 1 5 2 6 3

4

说明/提示

【数据范围】 对于 100% 的数据，6≤n≤13。