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.

题目背景

众所周知，众水、众方、众民与众律法的女王，伟大高尚的芙宁娜女士有三个动物朋友。请你分别默写出三个动物朋友的名字并发到云斗群里。

虽然你这么做并不会让自己的实力突飞猛进，但你会因此认识其余同样在玩《原神》的 OIers。

朋友是最珍贵的礼物。

题目描述

芙宁娜的生日是 10 月 13 日。在这天，卸任后的她成功研发出了一款蛋糕：超级矩阵蛋糕！

「超级矩阵蛋糕」可以被视为一个 $n$ 行 $m$ 列、每个单元格里的元素均为正整数的矩阵。勤奋的芙芙，在三个动物朋友的帮助下，成功烤了一堆不同规格的超级矩阵蛋糕。

为了判断蛋糕是否足够美丽，芙芙制定了如下打分规则。每次打分时，会对一个蛋糕打出一个二元组分数 $(A,B)$。

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

• 分数 $B$ 表示的是蛋糕中常量列的数量。如果该列中的值都相同，则该列是常量列。

而伟力无边的时间之魔神「派蒙（Paimon）」对蛋糕进行了偷吃！这使得蛋糕一些格子上的值缺失了。身为派蒙仆人的你，现在需要对矩阵上的缺失值进行填充。注意，只能填充正整数哦~

因此，被整个枫丹寄以厚望的你，现在需要填充该矩阵的缺失值，以创建可能的最佳矩阵得分。

矩阵“更好”的定义：

设有一个得分为 $(A, B)$ 的矩阵，另一个矩阵得分为 $(A',B')$。则若第一个矩阵更好，当且仅当满足以下条件之一：

• $A \gt A'$。
• $A = A'$ 且 $B \gt B'$ 。

输入格式

第 $1$ 行共两个正整数 $n$，$m$ ，描述蛋糕的尺寸。

第 $2\sim n + 1$ 行，每行包含 $m$ 个整数用于描述矩阵。矩阵中的每个值要么是正整数，要么是零。某个元素为0 则代表该位置存在缺失的值，需要填充。

输出格式

在单独一行上输出两个整数 $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

样例 #4

见附加测试用例 big_matrix100.in/.out。

big_matrix100.in

big_matrix100.out

样例 #5

见附加测试用例 big_matrix.in/.out。

big_matrix.in

big_matrix.out

提示

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

2 3 3 6 8
1 3 1 6 8
1 3 6 6 8

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

数据范围

对于前 $20\%$ 的数据，满足 $1\le n,m \le 4$。

对于前 $40\%$ 的数据，满足 $1\le n,m \le 100$。

对于另外 $20\%$ 的数据，满足 $v_{i,j} \neq 0$。

对于全部数据 $1 \le n,m \le 10^5,1\le n\times m \le 10^6,0 \le v_{i,j} \le 10^6$ 。

其中，$v_{i,j}$ 为输入的矩阵第 $i$ 行第 $j$ 列的数字。