eolymp
bolt
Try our new interface for solving problems
Problems

Square palindrome

Square palindrome

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 \textbf{n} rows of \textbf{n} letters each is a \textit{palindrome square} of size \textbf{n} if each row and each column of this square is a palindrome string. A string is a \textit{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. \InputFile The first line of the input file contains two integers \textbf{h} and \textbf{w} (\textbf{1} ≤ \textbf{h}, \textbf{w} ≤ \textbf{700}) - the height and width of the given rectangle of letters. The next \textbf{h} lines contain \textbf{w} lowercase English letters each --- the given rectangle of letters itself. \OutputFile 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 \textbf{1} to \textbf{h}, the columns are numbered from \textbf{1} to \textbf{w}. If there are several solutions, output any.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
5 10
abccbfghij
abccbfghij
abccbfghij
abccbfghij
abcdefghij
Output example #1
1 2 4 5