ASCII 퍼즐 맞추기

필리와 플로이가 퍼즐 놀이를 한다. 필리는 정사각형 칸이 $W \times H$ 격자로 그려진 직사각형 종이를 격자선을 따라 여러 조각으로 자르고, 조각을 돌리지 않은 채로 잘 섞어 놓는다. 플로이는 조각을 돌리지 않고 원래 직사각형으로 되돌려 놓아야 한다.

필리는 퍼즐이 제대로 만들어지도록 다음 규칙을 지키며 종이를 자른다. 먼저 정수 $w$, $h$, $n$을 고르고, 원래 종이의 너비를 $W = wn$ 칸, 높이를 $H = hn$ 칸으로 잡는다. 플로이는 $w$와 $h$는 알지만 $n$, $W$, $H$는 모른다. 이렇게 하면 원래 종이를 너비 $w$ 칸, 높이 $h$ 칸인 직사각형 $k = n^2$개로 나누는 자명한 퍼즐을 만들 수 있는데, $k > 1$인 자명한 퍼즐은 이 놀이에서 제대로 된 퍼즐로 보지 않는다. 실제로 자르는 조각은 이 $w \times h$ 직사각형을 바탕으로 하면서, 이웃한 조각 사이의 경계를 들쭉날쭉하게 만든 모양이다. 원래 $W \times H$ 종이를 자른 조각은 다음 조건을 모두 만족한다.

• 조각은 $k = n^2$개다.
• 각 조각은 구멍이 없고 상하좌우로 이어진 하나의 영역이다.
• 원래 종이의 모든 칸은 정확히 한 조각에 속한다.
• 각 조각은 자명한 퍼즐에서 대응하는 $w \times h$ 직사각형의 네 꼭짓점 칸을 포함한다.
• 각 조각의 칸은 대응하는 $w \times h$ 직사각형의 칸, 그 직사각형에 맞닿은 칸, 이웃한 직사각형의 내부 칸에서만 나온다.
• 이웃한 두 조각을 자른 선은 직선일 수 없다. 원래 종이의 테두리에 닿는 조각만 곧은 변이 있다.

이 조건에서 각 조각은 $(3w - 2) \times (3h - 2)$ 칸 직사각형 안에 들어간다. 그래서 각 조각은 대응하는 $w \times h$ 직사각형이 정확히 가운데에 오도록 $(3w - 2) \times (3h - 2)$ 격자로 주어진다.

예를 들어 $w = 4$, $h = 3$, $n = 3$이면 원래 종이는 $W \times H = 12 \times 9$ 칸이고, 자명한 퍼즐은 $4 \times 3$ 직사각형 $k = 9$개로 나뉜다. 가운데 직사각형에 대응하는 조각은 그 직사각형의 네 꼭짓점 칸을 반드시 포함하고, 나머지 칸은 그 직사각형에 맞닿은 칸이나 이웃 직사각형의 내부 칸에서만 온다. 이 조각을 담는 격자는 $(3w - 2) \times (3h - 2) = 10 \times 7$이다. 종이의 오른쪽 위 끝에 있는 조각도 같은 방식으로 주어진다.

플로이가 퍼즐을 맞추도록 도와주는 프로그램을 작성하시오.

첫째 줄에 정수 $k$, $w$, $h$가 주어진다. $k$는 퍼즐 조각의 개수이고, $w$와 $h$는 자명한 퍼즐 조각의 너비와 높이다. ($1 \le n \le 4$인 $n$에 대해 $k = n^2$, $3 \le w, h \le 5$)

다음으로 조각 $k$개의 모양이 주어진다. 각 조각은 문자 $3w - 2$개로 이루어진 줄 $3h - 2$개로 주어진다. 조각에는 앞에서부터 차례로 대문자 알파벳이 붙는다. 첫 번째 조각은 'A', 두 번째 조각은 'B'와 같은 식이다. 한 조각의 모양에는 문자 두 종류만 나온다. 그 조각의 알파벳은 조각에 속하는 칸을 뜻하고, 점('.')은 속하지 않는 칸을 뜻한다.

조각과 조각 사이는 빈 줄로 구분한다.

첫째 줄에 원래 종이의 크기 $W$와 $H$를 출력한다. 다음 $H$개 줄에는 줄마다 대문자 알파벳 $W$개를 출력해 퍼즐을 맞춘 결과를 나타낸다. 각 알파벳은 그 칸이 속한 조각을 뜻한다.

퍼즐을 맞추는 방법이 여러 가지면 사전순으로 가장 앞서는 방법을 출력한다. 두 방법을 비교할 때는 각 방법의 $H$개 줄을 위에서 아래로 이어 붙여 길이 $WH$인 문자열을 만들고, 두 문자열을 사전순으로 비교한다.

입력은 언제나 위 규칙대로 자른 퍼즐이므로 맞추는 방법이 적어도 하나 있다.