P4858 [PA 2013] Karty

Given an $n \times m$ rectangle, each cell is either `_` or `X`. Choose the largest possible $r \times c$ rectangle such that multiple $r \times c$ rectangles (overlapping is allowed) can cover all `X` cells, and do not cover any `_` cells.

The first line contains $n, m$, as described above. The next $n$ lines each contain a string of length $m$ describing the matrix.

Output one line with two integers $r, c$, separated by a space. If there are multiple choices with the maximum area, output the one with the smallest $r$.

Constraints: for $100\%$ of the testdata, $1 \le n, m \le 2.5 \times 10^3$. Translated by ChatGPT 5