這是一個互動式問題。
Taja 可以輕鬆贏得這個遊戲，但她的朋友們卻做不到。現在她邀請你來玩這個遊戲。
遊戲設備包含一個 $n \times n$ 的場地 ($5 \le n \le 40$)、一枚棋子、兩枚硬幣（COIN1, COIN2）、兩顆帶有方位方向的骰子（DICE1, DICE2），以及許多大小為一個單元格的方塊。
| 名稱 | 面數 | 面 |
|---|---|---|
COIN1. 移動硬幣 |
2 | SLIDE, RAM |
COIN2. 修改硬幣 |
2 | PLACE, REMOVE |
DICE1. 第一顆方向骰子 |
4 | N (北), S (南), W (西), E (東) |
DICE2. 第二顆方向骰子 |
8 | N (北), S (南), W (西), E (東), NW (西北), NE (東北), SW (西南), SE (東南) |
在遊戲開始前，棋子和一些方塊會被放置在場地上。接著玩家進行此類移動。首先，玩家選擇一枚硬幣並投擲它以決定動作。然後選擇一顆骰子並投擲它以決定方向 $dir$。之後會發生以下四種動作之一：
| 硬幣字串 | 動作 |
|---|---|
SLIDE |
沿著 $dir$ 方向在空單元格上移動棋子，直到棋子撞到方塊或迷宮邊界。 |
RAM |
沿著 $dir$ 方向在空單元格上移動棋子，直到撞到第一個方塊。然後將棋子和該方塊沿相同方向移動，直到移動的方塊撞到另一個方塊或場地邊界。 |
PLACE |
如果 $dir$ 方向上棋子旁邊的相鄰單元格為空且在場地內，則在此單元格放置一個方塊。 |
REMOVE |
如果 $dir$ 方向上棋子旁邊的相鄰單元格包含一個方塊且在場地內，則移除該單元格上的方塊。 |
遊戲目標是將棋子移動到終點單元格。此問題的一次查詢包含一次硬幣投擲和一次骰子投擲。
互動協定
首先，互動器會給出迷宮大小、迷宮內容以及終點單元格的座標。接著進行以下 4 步驟動作：
- 評測程式顯示棋子的座標，或通知棋子已到達終點單元格。
- 你的程式顯示硬幣名稱。
- 評測程式顯示硬幣上的動作名稱。
- 你的程式顯示骰子名稱。
- 評測程式顯示骰子上的方向名稱以及
RAM動作的額外資訊。
輸入格式
標準輸入的第一行包含一個整數 $n$ — 迷宮的大小。接下來 $n$ 行包含 $n$ 個字元 . (ASCII 46) 或 # (ASCII 35)，分別表示空單元格和有方塊的單元格。
下一行包含兩個整數 $r_f$ 和 $c_f$ — 終點單元格的列號和行號。左上角為 $(1, 1)$，右下角為 $(n, n)$。終點單元格和初始單元格皆為空。
接下來的群組描述每次移動：
- 群組的第一行包含兩個整數 $r, c$ — 棋子的列號和行號，若棋子到達終點則為 $(-1, -1)$。
- 下一行包含硬幣上顯示的動作名稱。
- 下一行包含骰子上顯示的方向名稱。
- 如果當前動作為
"RAM"，接下來的兩個字串包含兩個整數 $r_1, c_1$ 和 $r_2, c_2$，表示棋子撞到了座標為 $(r_1, c_1)$ 的方塊，並將該方塊移動到單元格 $(r_2, c_2)$。
北方向對應列號減少。南方向對應列號增加。西方向對應行號減少。東方向對應行號增加。 硬幣或骰子的每一面出現機率相同。
輸出格式
標準輸出應包含一對行：硬幣名稱和骰子名稱。硬幣名稱為字串 "COIN1" 或 "COIN2"。骰子名稱為字串 "DICE1" 或 "DICE2"。
請記得在列印每一行後刷新標準輸出。
範例
輸入格式 1
5 #.... ..... ..... ..... ..#.. 4 3 1 5 PLACE W 1 5 RAM S 6 5 6 5 5 5 RAM W 5 3 5 1 5 2 PLACE NE 5 2 RAM NE 4 3 2 5 3 4 REMOVE NE 3 4 PLACE S 3 4 SLIDE W 3 1 RAM S 5 1 5 1 4 1 SLIDE E -1 -1
輸出格式 1
COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN2 DICE2 COIN1 DICE2 COIN2 DICE2 COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN1 DICE1
範例迷宮的初始狀態
路徑的表示如下：
