Чарівний пончик
Ваш господар поїхав до міста на день. Ви могли б насолодитися спокійним днем без його докорів. Але він доручив вам приготувати тісто для пончиків до вечора. Він так любить пончики, що не може прожити без десятка щодня. Яка ж це робота на такий чудовий день.
Але минулого тижня ви підслухали магічне заклинання, яке використовував ваш господар. Настав час спробувати. Ви наклали заклинання на мітлу, що стояла в кутку кухні. Зі спалахом світла мітла виростила дві руки і дві ноги, і ожила. Ви наказали їй, і вона принесла з комори, і почала місити тісто. Заклинання спрацювало, і як швидко вона його місила!
Через кілька хвилин на кухонному столі була висока купа тіста. Цього було достатньо на наступний тиждень. "Добре, зупинись зараз." Ви наказали. Але вона не зупинилася. Допоможіть! Ви не знали заклинання, щоб зупинити її! Незабаром кухонний стіл був заповнений сотнями шматків тіста, і вона все ще працювала так швидко, як могла. Якщо ви не зупините її зараз, ви задихнетеся на кухні, заповненій шматками тіста.
Зачекайте, хіба ваш господар не записував свої заклинання в своїх зошитах? Ви пішли до його кабінету і знайшли зошит, в якому було записано заклинання припинення.
Але це не був кінець історії. Заклинання, записане в зошиті, не легко прочитати іншим. Він використовував пластикову модель пончика як зошит для запису заклинання. Він розділив поверхню моделі у формі пончика на квадратну сітку (Рисунок 1), і заповнив літерами (Рисунок 2). Він сховав заклинання так ретельно, що візерунок на поверхні виглядав безглуздо. Але ви знали, що він написав візерунок так, щоб заклинання "з'являлося" більше ніж один раз (див. наступний абзац для точних умов). Заклинання не обов'язково було написано зліва направо, але в будь-якому з 8 напрямків, а саме зліва направо, справа наліво, зверху вниз, знизу вгору, і в 4 діагональних напрямках.
Ви повинні знайти заклинання як найдовший рядок, що з'являється більше ніж один раз. Тут рядок вважається таким, що з'являється більше ніж один раз, якщо є квадратні послідовності, що мають рядок на пончику, які задовольняють наступні умови.
Кожна квадратна послідовність не перекриває сама себе. (Дві квадратні послідовності можуть ділити деякі квадрати.)
Квадратні послідовності починаються з різних квадратів та/або йдуть у різні напрямки.
Зверніть увагу, що паліндром (тобто рядок, який однаковий, чи читаєте ви його ззаду наперед чи навпаки), що задовольняє першу умову, "з'являється" двічі. Візерунок на пончику подано у вигляді матриці літер наступним чином.
ABCDEFGHIJKL
Зверніть увагу, що поверхня пончика не має кінців; верхня і нижня сторони, а також ліва і права сторони візерунка відповідно з'єднані. Можуть бути квадратні послідовності довші за вертикальну і горизонтальну довжини візерунка. Наприклад, з літери F у наведеному вище візерунку, рядки в найдовших неперекриваючихся послідовностях у напрямках 8 такі.
FGHEFKDEJCHIBGLAFJBFIDGJAHKBELCFEHGFALGBIHCJEDKFBJFCLEBKHAJGDI
Будь ласка, напишіть програму, яка знайде магічне заклинання, перш ніж ви задихнетеся шматками тіста для пончиків.
Вхідні дані
Вхідні дані - це послідовність наборів даних. Кожен набір даних починається з рядка з двома цілими числами h і w, які позначають розмір візерунка, за якими йдуть h рядків з w великими літерами від A до Z включно, які позначають візерунок на пончику. Ви можете припустити, що 3 ≤ h ≤ 10 і 3 ≤ w ≤ 20.
Кінець введення позначається рядком, що містить два нулі.
Вихідні дані
Для кожного набору даних виведіть магічне заклинання. Якщо є більше ніж один найдовший рядок однакової довжини, перший у словниковому порядку має бути заклинанням. Заклинання відоме як таке, що має принаймні дві літери. Коли заклинання не знайдено, виведіть 0 (нуль).