# 2467. Jigsaw Puzzles

The cows have taken up alphabetical jigsaw puzzles. In these puzzles with $R$ ($1 \le R \le 10$) rows and $C$ ($1 \le C \le 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:
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.

### 输入格式

• Line 1: Two space-separated integers: $R$ and $C$

• Lines 2..$RC+1$: Each line contains five space-separated entities: an integer serial number and four edge identifiers

### 输出格式

• Lines 1..$RC$: 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.

### 样例

Input
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

Output
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


### 提示

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

OUTPUT DETAILS:

3 人解决，6 人已尝试。

5 份提交通过，共有 11 份提交。

8.3 EMB 奖励。