Bounce

Time limit1sMemory limit128 MB

Summary

Find the shortest non-self-intersecting path on a hex grid from the top row to the bottom and back to the top row on the right, whose letters form a repeated pattern of given length. Example

Level: Medium6 of 10
Topics: DFS, Backtracking, Brute force, Implementation
Solved: No attempts yet

Problem



Figure 1	Figure 2

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.

Input

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.

Output

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.

Examples3

Example 1

Input

3 3 2
 B D C
C E B G
 B C B
3 5 4
 A B E B D
A C D C A D
 D B B B C
3 3 4
 B D C
C E B G
 B C B
3 4 4
 B D H C
C E F G B
 B C B C
0

Expected output

BCBCBC
BCBDBCBD
no solution
BCBCBCBC

Example 2
Input
```
3 3 2
 B D C
C E B G
 B C B
0
```
Expected output
```
BCBCBC
```

Example 3

Input

3 3 4
 B D C
C E B G
 B C B
0

Expected output

no solution