The Sorcerer's Donut

Your master went to town for the day, so you finally had a relaxed morning without his scolding. But before leaving he ordered you to prepare a batch of donut dough by evening. He loves donuts so much that he eats tens of them every day — what a chore on such a beautiful day.

Last week, though, you overheard one of his magic spells, and now was the time to try it. You cast the spell on a broomstick leaning in the corner of the kitchen. In a flash of light the broom sprouted two arms and two legs and came to life. You ordered it to work; it fetched flour from the storage and began kneading dough — astonishingly fast.

A few minutes later a tall pile of dough stood on the kitchen table, enough for a whole week. "OK, stop now," you ordered. But it did not stop — you never learned the spell to stop it! Soon hundreds of lumps of dough covered the table, and the broom kept working as fast as ever. If you could not stop it, you would be buried alive in dough.

Wait — doesn't your master write his spells in his notebooks? You rushed to his study and found the notebook that recorded the spell of cessation.

But the trouble was not over. The spell in the notebook is not meant to be read easily. He used a plastic donut model as his notebook: he divided the surface of the donut into a square mesh (Figure B.1) and filled every cell with a letter (Figure B.2). He hid the spell so cleverly that the pattern on the surface looks meaningless. Yet you know he wrote the pattern so that the spell appears more than once (the exact condition is given below). The spell is not necessarily written left to right; it may run in any of the 8 directions: left-to-right, right-to-left, top-to-bottom, bottom-to-top, and the 4 diagonals.

You must find the spell as the longest string that appears more than once. A string is said to appear more than once if there are square sequences on the donut spelling that string and satisfying both of the following conditions:

• Each square sequence does not overlap itself. (Two different square sequences may share squares.)
• The square sequences start from different squares and/or run in different directions.

Figure B.1: The donut before it is filled with letters, showing the mesh and the 8 possible spell directions.

Figure B.2: The donut after it is filled with letters.

Note that a palindrome (a string that reads the same forwards and backwards) that satisfies the first condition appears twice.

The pattern on the donut is given as a matrix of letters, for example:

ABCD
EFGH
IJKL

Because the donut's surface has no edges, the top and bottom rows are connected, and the left and right columns are connected (the pattern wraps around like a torus). A square sequence can therefore be longer than both the height and the width of the pattern. For example, starting from the letter F in the pattern above, the longest non-self-overlapping strings in the 8 directions are:

FGHE
FKDEJCHIBGLA
FJB
FIDGJAHKBELC
FEHG
FALGBIHCJEDK
FBJ
FCLEBKHAJGDI

Write a program that finds the magic spell before you are buried in donut dough.

The input is a sequence of datasets. Each dataset begins with a line containing two integers $h$ and $w$, the height and width of the pattern, followed by $h$ lines of $w$ uppercase letters (A–Z) describing the pattern on the donut. You may assume $3 \le h \le 10$ and $3 \le w \le 20$.

The end of the input is a line containing two zeros.

For each dataset, output the magic spell on its own line. If several longest strings share the same length, output the one that comes first in dictionary (lexicographical) order. The spell is guaranteed to be at least two letters long. If no spell exists, output 0 (zero).