eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Квадратный палиндром

Квадратный палиндром

Андрей только что совершил прорыв в информационных технологиях: он понял, как можно быстро находить наибольший квадратный палиндром в заданном прямоугольнике из букв. Сможете ли вы сделать то же самое? Квадрат, состоящий из \textbf{n} строк по \textbf{n} букв в каждой, называется \textit{квадратным палиндромом} размера \textbf{n}, если каждая строка и каждый столбец являются палиндромами. Строка называется \textit{палиндромом}, если ее первая буква совпадает с последней, вторая совпадает с предпоследней и т.д. \InputFile В первой строке входного файла содержатся два числа \textbf{h} и \textbf{w} (\textbf{1} ≤ \textbf{h}, \textbf{w} ≤ \textbf{700}) - высота и ширина заданного прямоугольника из букв. Далее \textbf{h} строк содержат по \textbf{w} букв - собственно заданный прямоугольник. \OutputFile Выведите координаты максимального квадратного палиндрома, являющегося частью заданного прямоугольника из букв. Выведите четыре числа: первую строку квадрата, первый столбец, последнюю строку и последний столбец. Строки нумеруются от \textbf{1} до \textbf{h}, столбцы нумеруются от \textbf{1} до \textbf{w}. Если существует несколько решений, выведите любое.
Лимит времени 2 секунды
Лимит использования памяти 256 MiB
Входные данные #1
5 10
abccbfghij
abccbfghij
abccbfghij
abccbfghij
abcdefghij
Выходные данные #1
1 2 4 5