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 nexttolast 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
