a071. 折紙密碼

題目描述

研究員在一張方格紙上寫下密碼字母，有些位置則留成透明空位 .。他將紙張接連對折，讓原本相距很遠的格子疊在一起，最後只從正面看折完的紙。你知道紙張原本的樣子和所有折疊指令，請重建最後看得到的圖案。

每次都沿著當前紙張的正中央對折。D 表示把上半部往下蓋在下半部，U 是把下半部往上蓋在上半部；R 是左半部往右蓋，L 是右半部往左蓋。折過去的半邊會以折線為軸呈鏡像排列，例如最靠近折線的格子會蓋到另一側最靠近折線的格子。折完後，被折到的那一半成為上層，紙張在該方向的長度減半。

同一位置若上下兩層都有字母，從正面只看得見上層字母；上層若為 .，就透過透明處看到下層，兩層都是 . 才仍是空位。後續的指令是對整張已經摺過的紙繼續操作，不能每次都回到最初的方格。輸出摺完後的尺寸和正面圖案。

輸入格式

第一行 R C，接著 R 行方格；下一行為折疊次數 Q；最後 Q 行各有一個方向字元 U、D、L 或 R。

限制

• 1 ≤ R, C ≤ 32；1 ≤ Q ≤ 5
• 每次上下折時，當下列數一定是偶數；每次左右折時，當下行數一定是偶數
• 方格只含大寫字母與 .

輸出格式

第一行輸出摺完後的 R' C'，接著輸出 R' 行、每行 C' 個字元的方格。

範例1

範例輸入：

2 2
A.
.B
1
D

範例輸出：

1 2
AB

上半部蓋到下半部：左邊看到上層 A，右邊的上層是透明格，所以看到下層 B。

範例2

範例輸入：

2 2
A.
.B
1
L

範例輸出：

2 1
A
B

右半部往左對折後，第一列的透明格露出 A，第二列的 B 覆蓋原本的空位。