出處: 2020 NPSC網際網路程式設計大賽高中組初賽pC

NPSC 遊戲公司最近開發了一款新的俄羅斯方塊遊戲。具體來說，這個遊戲由一個 \(N\times M\) 的網格組成。為了方便說明，以下把每個 \(1\times 1\) 格子稱為「單元」，最左上角的單元座標為 \((0,0)\)，最右下角的單元座標為 \((N-1,M-1)\)。在一開始，這個網格中會有任意數量的單元已經被先前落下的俄羅斯方塊占用。為了簡單起見，在本題當中不考慮方塊的消去，也就是有可能一整列的格子都是已經被占用的單元。

遊戲進行過程中，會有一個俄羅斯方塊開始落下。不同於傳統的俄羅斯方塊遊戲，在這個遊戲中每一個落下的俄羅斯方塊可能由 \(1\) 到 \(11\) 個單元組成，而這些單元中其中一個是「中心單元」。組成俄羅斯方塊的所有單元必定四方位連通，也就是說從該方塊的任一個單元開始，可以在該方塊內的單元中上下左右移動而抵達該方塊的另一個單元。俄羅斯方塊落下的規則如下：

• 以下以「發生碰撞」代表正在落下的方塊中任意一個單元與已經被占用的單元重疊、或超出遊戲網格的現象。
• 每隔一段時間，方塊會「自由落下」一格的距離，也就是把整個俄羅斯方塊往下平移一格。如果在平移之後發生碰撞，那麼方塊將被固定在平移前的位置，且整個落下的過程結束。
• 在落下的過程結束之前，可以在任何時間（不與自由落下同時）以任意順序進行任意次數的「平移」與「旋轉」操作，前提是每次操作之後都不能發生碰撞：
  • 「平移」有向左與向右兩種選項，分別是把整個俄羅斯方塊往左或往右平移一格。
  • 「旋轉」有逆時鐘或順時鐘兩種選項，分別是把整個俄羅斯方塊以「中心單元」為中心逆時鐘或順時鐘旋轉 90 度。

請你寫一個程式，輸入一個盤面，判斷一個正在落下的俄羅斯方塊在落下過程結束之後所有可能的位置與方向。

輸入格式

第一行有兩個以空白隔開的正整數 \(N,M\)，代表遊戲盤面的高度和寬度。

接下來有 \(N\) 行，每行有只由 \(\texttt{.oxX}\) 四種字元、長度為 \(M\) 的字串，代表初始的盤面。四種字元代表的意義如下：

• \(\texttt{X}\)：正在落下的方塊的中心單元。
• \(\texttt{x}\)：正在落下的方塊的非中心單元。
• \(\texttt{o}\)：一開始已經被佔用的單元。
• \(\texttt{.}\)：未被占用的單元。

• \(N,M\leq 1000\)

輸出格式

請輸出 \(X\) 行，代表該正在落下的方塊在落下過程結束後有 \(X\) 種可能的位置與方向。

每行請輸出三個以空白隔開的非負整數 \(x,y,d\)，代表一個可能的位置與方向，其中 \(x,y\) 代表該方塊\(\textbf{中心單元}\)最後位置的座標為 \((x,y)\)，而 \(d\) 代表方塊最後的方向，\(0,1,2,3\) 分別代表方塊一開始、逆時鐘旋轉 90 度、旋轉 180 度與順時鐘旋轉 90 度的方向。\(\textbf{注意就算旋轉之後方塊的外型與旋轉前相同，仍要視為有旋轉過。}\)

輸出必須按照 \((x,y,d)\) 的遞增順序排序。

範例輸入1

9 5
..x..
.oXo.
o.x.o
o.xo.
.o...
....o
o...o
o....
ooooo

範例輸出1

5 2 0
5 2 3
5 3 0
6 2 2
6 3 2

範例輸入2

3 3
xxx
xXx
xxx

範例輸出2

1 1 0
1 1 1
1 1 2
1 1 3