乳牛開始玩字母拼圖。拼圖有 $R$ 行（$(1 \le R \le 10)$）、$C$ 列（$(1 \le C \le 10)$），邊緣不是奇形紙板，而是字母。

每片有編號和 $4$ 個字母或邊界，須像普通拼圖對齊。偽字母 0（數字零）代表邊界。每片可有多個邊界，例如角片，甚至 $4\times1$ 拼圖一列的頂端片。以下六片是一種完成拼法，許多拼法之一，用線代替 0 標邊界：

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

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

相鄰片接邊字母相同，邊界正確在上、下與兩側。

每片由編號及順時針四邊表示，邊是 $a,\ldots,z$ 字母或 0。放置時可能須旋轉。

給定所有片，找至少一種完成方式。較大 $R$、$C$ 資料邊字母更豐富，故更容易解。

輸入格式

• 第 $1$ 行：空格分隔的整數 $R$ 和 $C$。

• 第 $2,\ldots,R\times C+1$ 行：每行空格分隔五項，整數編號及四邊標識。

輸出格式

• 第 $1,\ldots,R\times C$ 行：第 $R\times (i-1)+j$ 行描述第 $i$ 行第 $j$ 列的片，空格分隔五項：整數編號，接著上、右、下、左四邊標識。

範例

輸入格式 1

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

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

說明

輸入描述拼圖，但部分片相對範例解有旋轉。

如正文圖。亦有其他解，例如鏡像，檢查程式會驗證答案。

出題者：Rob Kolstad，2008