题目描述

奶牛们开始玩字母拼图了。在这种拼图中，拼图有 $R$ 行、$C$ 列，其中 $1 \le R \le 10$，$1 \le C \le 10$。拼图块的边缘并不是奇形怪状的纸板形状，而是字母。

每个拼图块都有一个编号和 $4$ 条边，每条边是一个字母或边界。它们必须像普通拼图一样对齐。伪字母 0（数字 $0$）表示边界。一个拼图块可以有多条边界，例如角块会有两条边界；在类似 $4 \times 1$ 这样的拼图中，某些拼图块也可能有多条边界。

下面是一组由 $6$ 个拼图块组成的拼图，它们以一种方式（可能有很多种方式）拼成了完整的拼图：

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

     +----d----+ +----a----+ +----e----+
     |         | |         | |         |
  0  |    2    b b    4    b b    6    |  0
     |         | |         | |         |
     +---------+ +---------+ +---------+
          0           0           0

注意，每个拼图块的边缘字母都要与相邻拼图块对应边缘的字母匹配；边界必须正确地出现在拼图的上边、下边、左边和右边。

每个拼图块用一个编号和按顺时针顺序列出的四条边表示，其中边可以是字母 a 到 z，也可以是 0。拼图块在放入拼图时可能需要旋转。

给定一组拼图块，请找出至少一种把它们拼成完整拼图的方式。对于较大的 $R$ 和 $C$，测试数据会更容易解决，因为它们的边缘字母更加多样。

输入格式

第一行包含两个用空格隔开的整数 $R$ 和 $C$。

接下来 $R \times C$ 行，每行包含 $5$ 个用空格隔开的内容：一个整数编号，以及四个边标识符。

输出格式

输出 $R \times C$ 行。

第 $R \times (i - 1) + j$ 行描述放在第 $i$ 行第 $j$ 列的拼图块，格式为一个整数和四个用空格隔开的边标识符：拼图块的编号，以及按照上、右、下、左顺序给出的四条边。

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 

提示

输入中的拼图块与样例解相比，虽然有些发生了旋转，但它们描述的是同一个拼图。

如题面图示所示。其他解法也是可能的，例如镜像解；评测程序会检查你的答案。