[PA2013] Karty

题目描述

给定 $n\times m$ 的矩形,每个点仅可能为 `_` 或 `X`, 选出一个最大的 $r\times c$ 的矩形,使得多个 $r\times c$ 的矩形能够(可以重叠的)覆盖全部 `X` 部分,不覆盖 `_` 部分。

输入输出格式

输入格式


第一行 $n,m$ 如题意所述。 接下来 $n$ 行,每行一个长为 $m$ 的字符串描述这个矩阵。

输出格式


输出一行,两个数 $r,c$,用空格隔开。 同时有多个面积最大的要输出 $r$ 最小的那个。

输入输出样例

输入样例 #1

4 5
_XXX_
XXXX_
XXXXX
_XXXX

输出样例 #1

2 3

说明

对于 $100\%$ 的数据,$1\le n,m\le 2.5\times 10^3$。