504. Square Palindrome
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
Andrew has just made a breakthrough in computer science: he realized how to quickly find the largest palindrome square on a given rectangle of letters. Can you do the same? A square consisting of
n rows of
n letters each is a
palindrome square of size
n if each row and each column of this square is a palindrome string. A string is a
palindrome string if its first letter is the same as its last letter, its second letter is the same as its next-to-last letter, and so on.
Input
The first line of the input file contains two integers
h and
w (1 ≤
h,
w ≤ 700) — the height and width of the given rectangle of letters. The next
h lines contain
w lowercase English letters each — the given rectangle of letters itself.
Output
Output the coordinates of the largest palindrome square that is a part of the given rectangle of letters. Output four integers: the first row of the square, the first column of the square, the last row of the square, the last column of the square. The rows are numbered from 1 to
h, the columns are numbered from 1 to
w. If there are several solutions, output any.
Example(s)
sample input | sample output |
5 10
abccbfghij
abccbfghij
abccbfghij
abccbfghij
abcdefghij
|
1 2 4 5
|