Bounce

This puzzle uses a cluster of hexagonal tiles packed together, each tile showing a single capital letter.

A bouncing path through the grid is a continuous path that

• uses no tile more than once,
• starts on a tile in the top row,
• includes at least one tile in the bottom row, and
• ends on a tile in the top row that lies to the right of the starting tile.

Continuous means every tile in the path shares an edge with the previous tile.

Each bouncing path spells out a sequence of letters. For example, the path in Figure 1 spells BCBCBC — that is, BC repeated three times. A path has a repetitive pattern of length $n$ when its whole letter sequence is exactly two or more copies of its first $n$ letters concatenated together. Figure 2 shows a repetitive pattern of length four: BCBD repeated twice. Your task is to find bouncing paths whose letter sequence forms a repetitive pattern of a given length.

Tile layout: the odd-numbered rows all have the same number of tiles as the first row. Each even-numbered row has one more tile than the odd rows, and its ends stick out past the odd rows on both the left and the right, so the hexagons interlock.

The input contains between one and twelve data sets, followed by a line containing only 0.

Each data set begins with a line of three space-separated integers $r$ $c$ $n$:

• $r$ — the number of rows in the hex pattern ($2 \le r \le 7$),
• $c$ — the number of tiles in each odd-numbered row ($2 \le c \le 7$),
• $n$ — the required pattern length ($2 \le n \le 5$).

The next $r$ lines give the capital letters on the tiles, one row per line, with the letters in a row separated by single blanks. Odd-numbered rows also begin with a leading blank so the printed grid mirrors how the hexagons fit together.

Print one line for each data set. If a bouncing path with a repetitive pattern of length $n$ exists, print the letter sequence spelled by the shortest such path. If no such path exists, print no solution.

Each data set is chosen so that the shortest solution path is unique whenever one exists.