题目描述

Alice有一个矩阵。Alice的矩阵有 $n$ 行和 $m$ 列，其中矩阵中的每个单元格都包含一个正整数。

Alice为矩阵分配一个得分 $(A,B)$：

$A$ 是单调不降行的数量。具体来说，如果该行中的值从左到右是 $v_1,v_2...v_m$ ，则如果 $v_1 \le v_2 \le ... \le v_m$ ，则该行是单调不降的。

$B$ 是常量列的数量。如果该列中的值都相同，则该列是常量列。

Alice 的矩阵是一个带有一些缺失值的矩阵。Alice 希望以一种方式填充缺失值，以创建可能的最佳矩阵的得分。

如果一个矩阵的得分比另一个矩阵的得分字典序更高，那么这个矩阵就更好。具体的，假设有一个得分为 $(A, B)$ 的矩阵和另一个得分为 $(A',B')$ 的矩阵。

第一个矩阵更好，如果满足以下条件之一：

$A \gt A'$ ，或者 $A = A',B \gt B'$ 。

输入格式

输入的第一行包含整数 $n$ 和 $m$ 。

接下来的 $n$ 行输入每行包含 $m$ 个整数，描述矩阵。矩阵中的每个值要么是正整数，要么是零，其中零代表缺失的值。

输出格式

在单独一行上输出两个整数A和B，表示可以创建的最佳矩阵的得分 $(A,B)$ 。

样例 #1

样例输入 #1

3 5
2 3 3 6 0
0 3 1 6 8
1 3 6 0 8

样例输出 #1

2 3

样例 #2

样例输入 #2

2 3
1 0 2
3 0 4

样例输出 #2

2 0

样例 #3

样例输入 #3

2 4
2 4 0 1
2 0 3 1

样例输出 #3

0 4

提示

对于样例1，可以将矩阵补充为

2 3 3 6 8

1 3 1 6 8

1 3 6 6 8

使得第 $1,7$ 行是单调不降行，第 $2,4,5$ 列为常量列，$A=2,B=3$ 。

对于 $20\%$ 的数据 $n,m \le 4$ 。

对于另外 $20\%$ 的数据 $n,m \le 100,v_{i,j} \neq 0$ 。

对于另外 $20\%$ 的数据 $n,m \le 100$ 。

对于全部数据 $1 \le n,m \le 10^5,nm \le 10^6,0 \le v_{i,j} \le 10^6$ ，$v_{i,j}$ 为输入的矩阵第 $i$ 行第 $j$ 列的数字。