题目描述

The cows have taken up alphabetical jigsaw puzzles. In these puzzles with R (1 <= R <= 10) rows and C (1 <= C <= 10) columns, the edges are not funny-shaped cardboard shapes but rather are letters.

Each piece has a serial number and 4 letters (or borders) that must be aligned as in a regular jigsaw puzzle. The pseudo-letter '0' (the digit 0) will represent a border (and a piece can have several borders if it is a corner piece or even the top of column in a, e.g., 4x1 puzzle). Below is a set of six pieces (the borders are marked with lines instead of '0's) assembled in one way (of many) that completes the puzzle:

+---+ +---+ +---+

| 1 c c 3 d d 5 | +-d-+ + a + +-e-+

+-d-+ +-a-+ +-e-+

| 2 b b 4 b b 6 | +---+ +---+ +---+

Note that each edge letter of each piece matches the border letter of the piece adjacent to it; the borders appear properly on the top, bottom, and sides.

Pieces are represented by a serial number and a clockwise list of their four edges (where edges are the letters a..z and 0). Pieces might require rotation when placed in the puzzle.

Given a set of pieces, find at least one way to assemble them into a puzzle. Test data for puzzles with larger R and C are easier to solve because they have a more varied set of edge letters.

奶牛们在玩按字母表顺序排列的拼图谜题.每道谜题有R(1≤R≤10)列C(1≤C≤10)行的拼图块,它们边缘是由字母或封闭边界组成,完成后的整副拼图外围是边界线,中间的边界是字母.

每块拼图块都有一个序列号和4个字母或者数字表示边界线(顺序为上右下左),在输入中,数字充当边界线.

拼图可以换位和旋转,完成后的拼图在边缘的块上靠近外围的是边界线,拼图完成后,一块拼图若与另一块相邻,它们的边界字母必须相同,以下是一系列已经成功完成的拼图谜题共6块.

输入格式

* Line 1: Two space-separated integers: R and C

* Lines 2..R*C+1: Each line contains five space-separated entities: an integer serial number and four edge identifiers

输出格式

* Lines 1..R*C: Line R*(i-1)+j describes the puzzle piece placed a row i, column j with an integer and five space-separated entities: the serial number of the puzzle piece and the four piece edge identifiers in the order top, right, bottom, left.

2 3 
1 c d 0 0 
2 0 d b 0 
3 c 0 d a 
4 b a b 0 
5 d 0 0 e 
6 0 0 b e 

1 0 c d 0 
3 0 d a c 
5 0 0 e d 
2 d b 0 0 
4 a b 0 b 
6 e 0 0 b 

提示

Describes the input puzzle although with some of the pieces rotated compared to the sample solution.

As shown in the diagram in the task text. Other solutions (like reflections) are possible; a grading program will check your answer.