该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

2014 年哈佛-麻省理工数学竞赛中一道题是这样的：将正整数 1, 2, ..., 64 填入 $8\times 8$ 的方格棋盘中，使得对任何 $1\le i < 64$，$i$ 和 $i+1$ 都必须填在两个具有公共边的方格中。求棋盘上对角线中所填数的和的最大值。（注意：两个对角线都要考虑；64 和1 也必须填在两个具有公共边的方格中。）

这题有点难…… 幸好我们并不要求你写程序解决这个问题。 你的任务是：对任一给定的数字填充方案，判定其是否满足填充的条件，并且在所有给出的方案中，找出满足条件的、且对角线数字和最大的那个方案。

输入格式

输入在一行中首先给出两个正整数 $n$（$\le 100$） 和 $m$（$\le 20$），分别为棋盘的规模（即棋盘有 $n\times n$ 个方格）和输入的方案数量。因为容易证明奇数 $n$ 一定不存在满足条件的解，所以题目保证给出的 $n$ 都是偶数。

随后给出 $m$ 个填充方案，每个方案占 $n$ 行，每行 $n$ 个不超过 $n^2$ 的数字。同行数字间以空格分隔。

输出格式

在一行中首先输出满足条件的、且对角线数字和最大的方案数。随后一行中按照递增序输出这些方案的编号（编号按输入的顺序从 1 到 $m$）。

注意每行数字间以 1 个空格分隔，行首尾不得有多余空格。

如果所有方案都不满足，在一行中输出 0

样例

4 5
16 1 2 3
15 14 13 4
10 11 12 5
9 8 7 6
16 1 2 3
15 14 13 4
10 11 12 5
9 8 7 10
15 16 1 2
14 13 4 3
11 12 5 6
10 9 8 7
3 4 5 6
2 13 12 7
1 14 11 8
16 15 10 9
10 5 4 3
7 12 13 2
8 11 14 1
9 6 15 16

2
1 4

限制

Java (javac) 时间限制 1100 ms 内存限制 256 MB

其他编译器 时间限制 400 ms 内存限制 64 MB