この問題はインタラクティブです。
Tajaは簡単にこのゲームに勝つことができますが、彼女の友人たちは誰も勝てませんでした。今、彼女はあなたにこのゲームをプレイすることを提案しています。
ゲームの用具は、$n \times n$ ($5 \le n \le 40$) のフィールド、駒、2枚のコイン（COIN1, COIN2）、方位が書かれた2つのサイコロ（DICE1, DICE2）、そして多数の1セルサイズのブロックで構成されています。
| 名前 | 面の数 | 面の内容 |
|---|---|---|
COIN1. 移動コイン |
2 | SLIDE, RAM |
COIN2. 変更コイン |
2 | PLACE, REMOVE |
DICE1. 方位サイコロ1 |
4 | N (北), S (南), W (西), E (東) |
DICE2. 方位サイコロ2 |
8 | N (北), S (南), W (西), E (東), NW (北西), NE (北東), SW (南西), SE (南東) |
ゲーム開始前に、駒といくつかのブロックがフィールド上に配置されます。その後、プレイヤーは以下のような手順で移動を行います。まず、プレイヤーはコインを1枚選び、それを投げてアクションを決定します。次に、サイコロを1つ選び、それを振って方向 $dir$ を決定します。その後、以下の4つのアクションのいずれかが発生します。
| コインの文字列 | アクション |
|---|---|
SLIDE |
駒を $dir$ 方向に、ブロックまたは迷路の境界に衝突するまで空きセルに沿って移動させる。 |
RAM |
駒を $dir$ 方向に、最初のブロックに衝突するまで空きセルに沿って移動させる。その後、駒とブロックを同じ方向に、移動中のブロックが別のブロックまたはフィールドの境界に衝突するまで移動させる。 |
PLACE |
駒の $dir$ 方向隣のセルが空きセルであり、かつフィールド内であれば、そのセルにブロックを配置する。 |
REMOVE |
駒の $dir$ 方向隣のセルにブロックがあり、かつフィールド内であれば、そのセルからブロックを取り除く。 |
目標は、駒をゴールセルに置くことです。 この問題における1クエリは、コインを1回投げ、サイコロを1回振ることに相当します。
インタラクション
最初に、インタラクタが迷路のサイズ、迷路の構成、およびゴールセルの座標を与えます。その後、以下の4ステップのアクションが発生します。
- 審査プログラムが駒の座標を表示するか、駒がゴールセルに到達したことを通知します。
- あなたのプログラムがコイン名を表示します。
- 審査プログラムがコインで出たアクション名を表示します。
- あなたのプログラムがサイコロ名を表示します。
- 審査プログラムがサイコロで出た方向名と、アクションが
RAMの場合の追加情報を表示します。
出力
標準出力は、コイン名とサイコロ名のペアで構成される必要があります。コイン名は文字列 "COIN1" または "COIN2" です。サイコロ名は文字列 "DICE1" または "DICE2" です。
各行を出力した後、標準出力をフラッシュすることを忘れないでください。
入力
標準入力の最初の行には、迷路のサイズを表す整数 $n$ が含まれます。続く $n$ 行には、$n$ 個の文字 . (ASCII 46) または # (ASCII 35) が含まれており、それぞれ空きセルとブロックのあるセルを表します。
次の行には、ゴールセルの行番号と列番号を表す2つの整数 $r_f$ と $c_f$ が含まれます。左上の角は $(1, 1)$、右下の角は $(n, n)$ です。ゴールセルと初期セルは空きセルです。
各移動について、以下のグループが続きます。
- グループの最初の行には、駒の行番号と列番号を表す2つの整数 $r, c$ が含まれます。駒がゴールセルに到達した場合は $(-1, -1)$ となります。
- 次の行には、コインで出たアクション名が含まれます。
- 次の行には、サイコロで出た方向名が含まれます。
- 現在のアクションが
"RAM"の場合、続く2つの文字列には2つの整数 $r_1, c_1$ と $r_2, c_2$ が含まれます。これは、駒が座標 $(r_1, c_1)$ のブロックに衝突し、そのブロックをセル $(r_2, c_2)$ に移動させたことを示します。
北方向は行番号の減少に対応します。南方向は行番号の増加に対応します。西方向は列番号の減少に対応します。東方向は列番号の増加に対応します。 コインやサイコロの各面は、等確率で出現します。
入出力例
入力 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