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

题目描述

This is one of the questions given in Harvard-MIT Math Tournament in 2014: The integers 1, 2, ..., 64 are written in the squares of a $8\times 8$ chess board, such that for each $1\le i <64$, the numbers $i$ and $i+1$ are in squares that share an edge. What is the largest possible sum that can appear along one of the diagonals? (Note: 64 and 1 must also be in squares that share an edge.) This is hard ... Fortunately you are not asked to solve this problem by writing a program. Your job is to check if any given plan of filling satisfies the constrains, and among all the given plans, find the one that satisfies the constrains with the largest diagonal sum.

输入格式

Each input file contains one test case. For each case, the first line gives 2 positive integers: $n$ ($\le 100$) and $m$ ($\le 20$), which are the size of the chess board (i.e. the chess board has $n\times n$ squares) and the number of plans given, respectively. Since it is simple to prove that there is no solution for any odd number $n$, it is guaranteed that the input $n$ is an even number. Then $m$ plans are given, each occupies $n$ lines, with $n$ numbers no more than $n^2$ given in each line. The numbers in a line are separated by a space.

输出格式

For each test case, first print in a line the number of plans that satisfy the constrains with the largest diagonal sum. Then output in the next line in increasing order the indices of these plans (the plans are indexed from 1 to $m$ as in the input order). Note: all the numbers in a line must be separated by 1 space, and there must be no extra space at the beginning or the end of the line.

样例

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