You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

最大公约数矩阵

题目描述

给你一个$n*m$的矩阵$a$，让你从中找到一个最大的子矩阵，使得其中所有元素的最大公约数大于1，并且求出满足大小最大的情况下，最大的那个最大公约数。

输入格式

第一行两个正整数$n,m$。 后面$n$行，每行$m$个非负整数表示这个矩阵。

输出格式

两行，第一行一个个正整数$s$表示满足条件的最大子矩阵面积。 第二行一个正整数表示这个面积的子矩阵的最大公约数的最大值。

样例 #1

样例输入 #1

3 3
8 18 24
12 30 15
9 10 5

样例输出 #1

4
5

样例 #2

样例输入 #2

5 5
2 4 6 9 21
10 8 16 24 36
14 12 8 12 24
18 8 4 20 28
30 28 18 14 12

样例输出 #2

20
2

样例 #3

样例输入 #3

5 3
1 1 1
4 4 4
6 6 6
9 9 9
12 12 12

样例输出 #3

9
3

提示

样例解释1：

选取左上4个元素，右上4个元素，右下4个元素都满足条件，其中左上4个元素的最大公约数是2，右上4个元素的最大公约数是3，右下4个元素的最大公约数是5，故第2行输出是5。

数据范围

对所有数据满足$1≤n,m≤500,1≤a_{i,j}≤100$，保证存在面积大于1的解。

特殊性质：每一行都是一组相同的自然数。