QOJ.ac

QOJ

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

#6069. Cards [A]

Statistics

Bajtazar works as a programmer in the 1960s. It is tedious work, as he enters programs into the computer not via a keyboard, but using punch cards. A card of size $n \times m$ consists of $n \cdot m$ identical rectangular fields arranged in $m$ columns and $n$ rows. Each field can be punched. The pattern of holes on the card encodes the program's content. The figure below shows an example of a $4 \times 5$ card. The holes in the fields are marked with black rectangles.

Bajtazar already has the program in his head and knows which fields should be punched. However, he would like to prepare the card as efficiently as possible. To this end, he decided to create a rectangular matrix that, when applied to the card, will punch all fields in a chosen $a \times b$ fragment (i.e., fields belonging to the intersection of $a$ consecutive rows and $b$ consecutive columns). The size of this matrix should be chosen such that it can be used to create a punch card having holes exactly in the places Bajtazar planned. At the same time, the matrix should be as large as possible. Since the fields on the card are not square, the matrix cannot be rotated (e.g., to obtain a matrix of size $b \times a$).

Programming computers takes much less time today than it used to, which is why Bajtazar has asked you to write a program that will determine the dimensions of the largest matrix that can be used to write his program on the card.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n,m \le 2\,500$). They denote the number of rows and columns on the punch card, respectively. The next $n$ lines contain the description of Bajtazar's program. Each of these lines consists of $m$ characters "_" or "X". The character "X" denotes a card field that should be punched, while "_" denotes a field that should not be punched. You may assume that the card description contains at least one "X" character.

Output

Your program should output two integers $a$ and $b$ describing the dimensions of the matrix that can be used to create the card described in the input. The product of these two numbers should be as large as possible. If there are multiple correct answers, your program should output the one with the smallest value of $a$.

Examples

Input 1

4 5
_XXX_
XXXX_
XXXXX
_XXXX

Output 1

2 3

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.