ASCII Puzzle

Fili and Floi play a puzzle game. Fili takes a rectangular piece of paper ruled into a $W \times H$ grid of square cells, cuts it into pieces along the grid lines, and shuffles the pieces without rotating any of them. Floi has to put the pieces back together into the rectangle, again without rotating them.

Fili follows a few rules while cutting so that the puzzle is well formed. Fili first picks integers $w$, $h$, and $n$, and the original paper is $W = wn$ cells wide and $H = hn$ cells tall. Floi knows $w$ and $h$, but not $n$, $W$, or $H$. The paper can therefore be cut into a trivial puzzle of $k = n^2$ rectangles, each $w$ cells wide and $h$ cells tall. For $k > 1$ that trivial puzzle does not count as well formed in this game. The real pieces are based on those $w \times h$ rectangles, with jagged borders between adjacent pieces. Formally, the pieces cut out of the $W \times H$ paper satisfy all of the following:

• There are $k = n^2$ pieces.
• Each piece is a simple 4-connected region of cells without holes.
• Each cell of the original $W \times H$ paper belongs to exactly one piece.
• Each piece contains the four corner cells of the corresponding $w \times h$ rectangle of the trivial puzzle.
• The cells of a piece come only from the corresponding $w \times h$ rectangle, from the cells adjacent to that rectangle, and from the interior cells of the adjacent rectangles.
• The cut between two adjacent pieces is never straight. Only pieces that lie on the border of the original paper have straight sides.

It follows that each piece fits inside a rectangle of $(3w - 2) \times (3h - 2)$ cells, so each piece is given as a $(3w - 2) \times (3h - 2)$ grid with its own $w \times h$ rectangle exactly in the center.

For example, with $w = 4$, $h = 3$, and $n = 3$ the original paper is $W \times H = 12 \times 9$ cells and the trivial puzzle splits it into $k = 9$ rectangles of $4 \times 3$ cells. The piece that corresponds to the central rectangle always contains that rectangle's four corner cells, and its other cells come only from cells touching that rectangle or from interior cells of the neighbouring rectangles. The grid that describes this piece is $(3w - 2) \times (3h - 2) = 10 \times 7$ cells. The piece in the upper right corner of the paper is given the same way.

Write a program that helps Floi solve the puzzle.

The first line contains three integers $k$, $w$, and $h$. Here $k$ is the number of pieces, and $w$ and $h$ are the width and the height of a trivial puzzle piece ($k = n^2$ for some $1 \le n \le 4$, $3 \le w, h \le 5$).

The shapes of the $k$ pieces follow. Each piece is described by $3h - 2$ lines of $3w - 2$ characters. The pieces are labelled with consecutive uppercase English letters: the first piece is 'A', the second is 'B', and so on. A single description uses only two characters. The letter of the piece marks a cell that belongs to it, and a dot ('.') marks a cell that does not.

Empty lines separate the pieces.

Print $W$ and $H$, the size of the original piece of paper, on the first line. On the following $H$ lines print $W$ uppercase letters each, describing the assembled puzzle. Every letter tells which piece that cell belongs to.

If the puzzle can be assembled in more than one way, print the lexicographically smallest one. To compare two ways, join the $H$ lines of each of them from top to bottom into one string of $WH$ letters, then compare those two strings lexicographically.

The input always describes a puzzle that was cut under the rules above, so at least one arrangement exists.