题目描述

Fili and Floi play a puzzle game. Fili takes a rectangular piece of paper that is lined with a $W \times H$ grid of square cells, cuts it into pieces on its grid lines, and carefully shuffles the pieces so that pieces do not rotate. Floi has to recombine the pieces back into the rectangle without rotating them.

Fili observes a number of constraints while cutting an original paper into pieces to make sure that the resulting puzzle is well-formed. First of all, Fili picks three integer numbers $w , h$ , and $n$ , so that an original rectangular paper has a width of $W = w_n$ cells and a height of $H = h_n$ cells. Here $w$ and $h$ are known to Floi, but $n , W$ , and $H$ are not. This way, the original rectangular piece of paper can be cut into a trivial puzzle of $k = n^{2}$ rectangles with a width of $w$ cells and a height of $h$ cells each. However, this trivial puzzle for $k > 1$ is not considered a well-formed puzzle for this game. Instead, the pieces int which the original rectangle is cut are based on these trivial $w \times h$ cell rectangles with the jagged edges between the adjacent pieces. Formally, the pieces into which the original $W \times H$ paper is cut satisfy the following constraints of a well-formed puzzle:

There are $k = n^{2}$ pieces.

Each piece is a simple $4-connected$ region of cells without holes.

Each cell of the original rectangular $W \times H$ paper is a part of exactly one piece.

Each piece contains four corners of the corresponding $w \times h$ rectangle in the trivial puzzle for the original paper.

The cells of each piece can come only from the corresponding $w \times h$ rectangle in the trivial puzzle, from the cells adjacent to this rectangle, and from the interior cells of the adjacent rectangles in the trivial puzzle.

The cut between two adjacent pieces cannot be straight. Only pieces that lie on the border of the original $W \times H$ paper have straight sides.

The corollary of these constraints is that each piece of a well-formed puzzle fits into a rectangle of (3w $− 2) \times$ (3h $− 2)$ cells. Moreover, the description of each piece will be given as a (3w $− 2) \times$ (3h $− 2)$ grid of cells in such a way, that the corresponding $w \times h$ rectangle of the trivial puzzle is exactly in the center.

The picture below to the left shows a sample rectangular piece of paper that is lined with a $W \times H = 12 \times 9$ square grid of cells and is cut into a trivial puzzle of $k = 9$ rectangles with a width of $w = 4$ cells and a height of $h = 3$ cells each with bold dashed lines. The corners of the central $3 \times 4$ piece of this trivial puzzle are shown in black. They have to be a part of the central piece of any well-formed puzzle. The other potential cells of the central piece of a well-formed puzzle are shown in gray. The bold black line shows (3w $− 2) \times$ (3h $− 2) = 10 \times 7$ rectangular region that will be describing this central piece. The picture to the right shows the same for the piece in the upper-right corner of the puzzle.

Your task is to help Floi solve the puzzle.

输入格式

The first line of the input file contains there integers $k , w$ and $h$ . Here $k$ is the number of pieces in the puzzle, $w$ is a width and $h$ is a height of a trivial puzzle piece $(k = n^{2}$ for $1 \le n \le 4 , 3 \le w , h \le 5)$ . The rest of the input file contains descriptions of $k$ pieces of a well-formed puzzle. Each piece is described by 3h $− 2$ lines that contain 3w $− 2$ characters each. Pieces are labeled with a consecutive English letters in uppercase (1st piece -- $‘A', 2nd$ piece -- $‘B',$ and etc). Each piece description uses only two characters on its 3h $− 2$ lines of 3w $− 2$ characters. The English letter corresponding to the piece denotes a cell that is a part of this piece, while $‘. '$ (dot) character denotes a cell that is not.

Empty lines separate different pieces.

输出格式

The first line of the output file shall contain $W$ and $H$ -- the size of the original piece of paper that was cut into the puzzle pieces. The following $H$ lines shall contain $W$ English letters each, describing the solution of the puzzle. Letters denote the cells that belong to the corresponding puzzle pieces. If there are multiple ways to solve the puzzle, then print any solution.

题目大意

Fili 和 Floi 在玩一个拼图游戏。Fili 准备了一个被划分为 $W\times H$ 个格子的矩形纸片，并沿着格子的边缘将纸片剪成了若干个小片，然后小心地重排这些纸片使得纸片没有被旋转。

Fili 观察到满足一些限制的裁剪方案会产生一个良好的拼图游戏：首先，Fili 选择了三个整数 $w,h,n$，使得原先矩形的长宽分别满足 $W = wn$ 和 $H = hn$。此处 $w,h$ 是 Floi 知道的。这样最初的拼图游戏就可以变为 $k=n^2$ 个 $w\times h$ 的矩形构成的平凡的拼图。然而，平凡的拼图游戏不被认为是良好的。一个良好的游戏被定义为在拼图间有着参差不齐的边界（译者注：即有缺口和凸起的拼图）的游戏。更形式化地，一个将 $W\times H$ 纸片裁剪成拼图游戏的裁剪方案被认为是良好的当且仅当它满足以下性质：

• 有 $k=n^2$ 片拼图，且该拼图的每一块与平凡的拼图中的 $n^2$ 个 $w\times h$ 矩形一一对应。
• 每片拼图是一个没有洞的四联通区域。
• 每个原 $W\times H$ 纸片的格子属于恰好一片拼图。
• 每片拼图都包含了其对应的 $w\times h$ 矩形的四个角落处的格子。
• 每片拼图只能包含有：其对应的 $w\times h$ 矩形中的格子，与该矩形相邻的格子，以及与该矩形相邻矩形的内部格子。
• 两个相邻的拼图的边界不是直的。只有恰好贴着纸片边界的拼图的边界是直的。

注意到每块拼图必然包含于以其对应的 $w\times h$ 矩形为中心的一个 $(3w-2)(3h-2)$ 大小的矩形，于是输入文件以此方式给出。

你需要找到拼图的一种拼法。

$k=n^2$，$1\le n\le 4$，$3\le w,h\le 5$。

4 4 3
..........
..........
...AAAA...
...AAAAAA.
...A.AA...
..........
..........

..........
..........
...BBBB...
.....BB...
...BBBB...
....BB....
.....B....

..........
..........
...C..C...
..CCC.C...
...CCCC...
..........
..........

..........
....D.....
...DDDD...
...DDD....
...DDDD...
..........
..........

8 6
AAAABBBB
AAAAAABB
ADAABBBB
DDDDCBBC
DDDCCCBC
DDDDCCCC

提示

Time limit: 1 s, Memory limit: 128 MB.