QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 10

#6069. Karty [A]

الإحصائيات

Bajtazar在20世纪60年代是一名程序员。这是一项艰苦的工作,因为他不是通过键盘而是通过穿孔卡片将程序输入计算机。一张大小为 $n \times m$ 的卡片由 $n \cdot m$ 个相同的矩形字段组成,排列成 $m$ 列 $n$ 行。每个字段都可以被穿孔。卡片上的孔洞图案编码了程序内容。下图显示了一个 $4 \times 5$ 的示例卡片。字段中的孔洞用黑色矩形标记。

problem_6069_1.gif

Bajtazar已经有了程序,并且知道哪些字段应该被穿孔。但是,他想尽可能高效地准备卡片。为此,他决定制作一个矩形模板,该模板放置在卡片上时,可以在Bajtazar选择的 $a \times b$ 大小的区域(即属于 $a$ 个连续行和 $b$ 个连续列的交集的字段)中穿孔所有字段。该模板的尺寸应选择得当,以便使用它可以制作出孔洞位置与Bajtazar计划的完全一致的穿孔卡片。同时,模板应尽可能大。由于卡片上的字段不是正方形的,因此模板不允许旋转(例如,获得 $b \times a$ 大小的模板)。

现在,计算机编程比以前花费的时间少得多,因此Bajtazar请你编写一个程序,确定用于将他的程序写入卡片的最大模板的尺寸。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n,m \le 2\,500$)。它们分别表示穿孔卡片上的行数和列数。接下来的 $n$ 行包含Bajtazar程序的描述。每行由 $m$ 个字符 "_" 或 "X" 组成。字符 "X" 表示应该被穿孔的卡片字段,而 "_" 表示不应被穿孔的字段。你可以假设卡片描述中至少包含一个字符 "X"。

输出格式

你的程序应该输出两个整数 $a$ 和 $b$,描述可用于制作输入中描述的卡片的模板的尺寸。这两个数的乘积应该尽可能大。如果存在多个正确答案,你的程序应该输出 $a$ 值最小的那个。

示例

输入

4 5
_XXX_
XXXX_
XXXXX
_XXXX

输出

2 3