【問題G21】拼圖。            [回前頁]

又到了機器人大賽的時間。為了讓自己設計的機器人能在大賽中獲得評審的青睞，參賽者無不攪盡腦汁，讓自己的機器人能有最特殊的功能。

身為拼圖迷的你最希望的就是做出能跟人比賽拼圖的機器人了。但是你很快地發現，讓機器人能判斷兩片拼圖上的圖案是否連續實在是件很困難的事情。所幸，機器人可以準確地分析拼圖四面的角或是缺口。縱使機器人無法辨別兩片拼圖的圖案是否連續，但一片拼圖的一個角能不能搭上另一片拼圖的一個缺口，機器人卻可以輕鬆判斷。憑藉著辨別拼圖的角和缺口的能力，你設計的機器人是否能和人一樣完成一幅拼圖呢？

輸入檔說明

輸入檔包含多筆的測試資料。

每一筆測試資料的第一行有兩個數字r c (1 <= r*c <= 252)，分別表示拼圖的上到下的高一共是r片拼圖，左到右的寛度是c片拼圖。接下來一共有r*c行，每一行有8個字元，表示一片拼圖的資訊。前4個字元依序表示拼圖的左､上､右､下邊。大寫字母表示該邊為角，小寫字母表示該邊為缺口，一個減號則表示該邊是平的(表示這片拼圖是邊框中的其中一塊)。字母相同的角可以和缺口相接：例如1片拼圖的右側為A，另一片的左側為a，則兩片拼圖可以左右相接。

後4個字元則表示拼圖的圖案，圖案除了英文字母外也可能是空白字元。旋轉一片拼圖後，拼圖上的圖案看起來是不一樣的。因此4個字元分別表示拼圖四個方向的圖案。如果拼圖不需要旋轉，則該片拼圖的圖案即是後4個字元中的第1個。若拼圖需要順時針旋轉90度，則拼上拼圖的圖案則是第2個，再旋轉90度則是第3個，餘以類推。

第一片拼圖(每筆測試資料的第二行)一定剛好是最左上角的拼圖，其他拼圖的順序則不固定。你的機器人可以從第一片拼圖開始往後拼完整幅拼圖。除了第一片拼圖以外，其他拼圖可能需要先經過旋轉才能拼上去。為了讓大家清楚了解拼圖的表示法，下方的範例輸入資料第一筆為一個未被打亂的拼圖，拼圖的次序由左到右，由上到下。

當測試資料輸入的r和c皆為0時表示輸入檔結束，程式不需要對這一行輸入作處理。

輸出檔說明

對於每一筆測試資料，請將拼好的拼圖圖案輸出。每幅拼圖之後請輸出一個空行來作分隔。(你可以假設每幅拼圖只有一種拼法能完全拼圖。)

範例輸入

範例輸出