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