바운스

이 퍼즐은 여러 개의 육각형 타일을 빈틈없이 붙여 놓은 것으로, 각 타일에는 대문자 한 글자가 적혀 있다.

격자 위의 바운스 경로(bouncing path) 는 다음 조건을 모두 만족하는 연속된 경로이다.

• 같은 타일을 두 번 이상 지나지 않는다.
• 맨 윗줄의 타일에서 시작한다.
• 맨 아랫줄의 타일을 적어도 하나 지난다.
• 시작 타일보다 오른쪽에 있는 맨 윗줄 타일에서 끝난다.

연속이라는 것은 경로의 다음 타일이 항상 바로 앞 타일과 한 변을 공유한다는 뜻이다.

각 바운스 경로는 하나의 글자열을 만든다. 예를 들어 그림 1의 경로가 만드는 글자열은 BCBCBC, 즉 BC가 세 번 반복된 것이다. 경로의 글자열 전체가 앞의 $n$글자를 두 번 이상 이어 붙인 것과 정확히 같을 때, 그 경로는 길이 $n$의 반복 패턴을 가진다고 한다. 그림 2는 BCBD를 두 번 반복한 길이 4의 반복 패턴을 보여 준다. 주어진 길이의 반복 패턴을 가지는 바운스 경로를 찾는 것이 목표이다.

타일 배치: 홀수 번째 줄은 모두 첫 줄과 같은 개수의 타일을 가진다. 짝수 번째 줄은 홀수 줄보다 타일이 하나 더 많으며, 양쪽 끝이 홀수 줄보다 왼쪽과 오른쪽으로 각각 튀어나와 육각형들이 서로 맞물리도록 배치된다.

입력은 1개 이상 12개 이하의 데이터 집합으로 이루어지며, 마지막에는 0만 적힌 줄이 온다.

각 데이터 집합의 첫 줄에는 공백으로 구분된 세 정수 $r$ $c$ $n$ 이 주어진다.

• $r$ — 육각 격자의 줄 수 ($2 \le r \le 7$)
• $c$ — 홀수 번째 줄에 있는 타일의 개수 ($2 \le c \le 7$)
• $n$ — 필요한 반복 패턴의 길이 ($2 \le n \le 5$)

이어지는 $r$개의 줄에는 타일에 적힌 대문자가 한 줄에 한 행씩 주어지며, 한 줄 안의 글자들은 하나의 공백으로 구분된다. 홀수 번째 줄은 육각형이 맞물리는 모양을 나타내기 위해 맨 앞에도 공백이 하나 붙는다.

각 데이터 집합마다 한 줄을 출력한다. 길이 $n$의 반복 패턴을 가지는 바운스 경로가 있으면, 그러한 경로 중 가장 짧은 경로가 만드는 글자열을 출력한다. 그런 경로가 없으면 no solution 을 출력한다.

각 데이터 집합은 해가 존재할 경우 가장 짧은 해 경로가 유일하도록 선택되어 있다.