마법사의 도넛

문제

주인님이 하루 동안 마을에 나가셨습니다. 오랜만에 잔소리 없이 느긋한 아침을 보낼 수 있게 되었지요. 하지만 주인님은 떠나기 전에 저녁까지 도넛 반죽을 만들어 두라고 시키셨습니다. 도넛을 무척 좋아하는 주인님은 매일 수십 개씩 드셔야 하니, 이 좋은 날에 참 성가신 일입니다.

그런데 지난주에 주인님이 외우던 마법 주문을 우연히 엿들었습니다. 지금이 바로 시험해 볼 기회였습니다. 부엌 구석에 세워져 있던 빗자루에 주문을 걸자, 번쩍이는 빛과 함께 빗자루에서 팔 두 개와 다리 두 개가 돋아나 살아 움직이기 시작했습니다. 일하라고 명령하자 빗자루는 창고에서 밀가루를 가져와 반죽을 치대기 시작했는데, 그 속도가 놀랍도록 빨랐습니다.

몇 분 지나지 않아 식탁 위에는 반죽이 산더미처럼 쌓였습니다. 한 주 동안 쓰고도 남을 양이었지요. "이제 그만!" 하고 명령했지만 빗자루는 멈추지 않았습니다. 멈추게 하는 주문을 몰랐던 것입니다! 곧 식탁은 수백 덩이의 반죽으로 뒤덮였고, 빗자루는 여전히 온 힘을 다해 일했습니다. 지금 멈추지 못하면 반죽에 파묻혀 숨이 막힐 지경이었습니다.

가만, 주인님은 주문을 공책에 적어 두지 않으셨던가요? 서재로 달려가 '멈춤의 주문'이 적힌 공책을 찾아냈습니다.

하지만 이야기는 그것으로 끝이 아니었습니다. 공책에 적힌 주문은 남이 쉽게 읽을 수 없게 되어 있었습니다. 주인님은 공책 대신 도넛 모양의 플라스틱 모형을 사용했습니다. 도넛의 겉면을 정사각형 격자로 나누고(그림 B.1) 각 칸을 글자로 채운 것입니다(그림 B.2). 표면의 무늬가 아무 의미 없어 보이도록 주문을 아주 교묘하게 숨겨 두었습니다. 그러나 주인님이 주문이 두 번 이상 나타나도록 무늬를 만들었다는 사실을 당신은 알고 있습니다(정확한 조건은 아래에 있습니다). 주문이 반드시 왼쪽에서 오른쪽으로 적혀 있는 것은 아니며, 8방향(왼→오, 오→왼, 위→아래, 아래→위, 그리고 대각선 4방향) 중 어느 방향으로든 적혀 있을 수 있습니다.

당신은 주문을 두 번 이상 나타나는 가장 긴 문자열로서 찾아내야 합니다. 어떤 문자열이 '두 번 이상 나타난다'는 것은, 그 문자열을 이루는 칸의 수열들이 도넛 위에 존재하며 다음 두 조건을 모두 만족하는 경우를 말합니다.

각 칸의 수열은 자기 자신과 겹치지 않는다. (서로 다른 두 수열은 일부 칸을 공유해도 된다.)
각 수열은 서로 다른 칸에서 시작하거나, 서로 다른 방향으로 나아간다.

그림 B.1: 글자를 채우기 전의 도넛. 격자와 주문이 적힐 수 있는 8방향을 보여 준다.

그림 B.2: 글자를 채운 뒤의 도넛.

앞뒤로 읽어도 똑같은 문자열(회문)이 첫 번째 조건을 만족하면 두 번 나타나는 것으로 셈합니다.

도넛 위의 무늬는 다음과 같이 글자의 행렬로 주어집니다.

ABCD
EFGH
IJKL

도넛의 겉면에는 끝이 없으므로, 무늬의 위·아래 변이 서로 이어져 있고 좌·우 변도 서로 이어져 있습니다(무늬가 도넛처럼 상하좌우로 순환합니다). 따라서 칸의 수열은 무늬의 세로 길이와 가로 길이보다 더 길어질 수도 있습니다. 예를 들어 위 무늬에서 글자 F부터 시작하여 8방향으로 뻗어 나가는, 자기 자신과 겹치지 않는 가장 긴 문자열은 다음과 같습니다.

FGHE
FKDEJCHIBGLA
FJB
FIDGJAHKBELC
FEHG
FALGBIHCJEDK
FBJ
FCLEBKHAJGDI

도넛 반죽에 파묻히기 전에 마법 주문을 찾아내는 프로그램을 작성하세요.

입력

입력은 여러 개의 데이터셋으로 이루어집니다. 각 데이터셋의 첫 줄에는 무늬의 세로와 가로 크기를 나타내는 두 정수 $h$와 $w$가 주어지고, 이어서 도넛 위의 무늬를 나타내는 $h$개의 줄이 주어집니다. 각 줄은 대문자 A–Z로 이루어진 $w$개의 글자입니다. $3 \le h \le 10$이고 $3 \le w \le 20$임이 보장됩니다.

입력의 끝은 두 개의 0이 적힌 줄로 표시됩니다.

출력

각 데이터셋에 대해 마법 주문을 한 줄에 하나씩 출력합니다. 가장 긴 문자열이 여러 개이고 길이가 같다면, 사전 순으로 가장 앞서는 것을 출력합니다. 주문은 항상 두 글자 이상임이 보장됩니다. 주문이 존재하지 않으면 0(영)을 출력합니다.