D: 遭難

問題

$H * W$ のグリッドで表される地図が与えられる。各マスは '#' か '.' であり、前者は陸地であることを、後者は海であることを示している。

以下のように上下左右に隣接している陸地の集合を島と呼ぶ。

.....
.###.
..##.
..#..
.....

陸地 $6$ マスの島。

......
.##.#.
....#.
......

陸地 $2$ マスの島が $2$ つ。

与えられる地図は、以下の条件を満たす。

地図の端 $1$ マスは必ず '.' である。
同じ形の島が二つ以上存在することはない。
つまり、島に含まれる陸地のうち、最も上にあり、その中で最も左にある陸地を基準とした陸地の座標集合が等しい島は存在しない。
全ての '.' マスは連結である。つまり、以下のような島は存在しない。

.....
.###.
.#.#.
.###.
.....

陸地のどこかにAORイカちゃんがいる。あなたの目標は、AORイカちゃんが最初にいたマスを当てることである。そのために、あなたは次のクエリを繰り返し送ることができる。

'U', 'D', 'L', 'R' のうち、ひとつを選ぶ。AORイカちゃんの現在位置を $c_{y, x}$ とすると、それぞれ $c_{y - 1, x},\ c_{y + 1, x},\ c_{y, x - 1},\ c_{y, x + 1}$ に移動するように指示することができる。
移動先が '.' である場合、AORイカちゃんは "NO" を返し、移動しない。そうでない場合、AORイカちゃんは "YES" を返し、指定したマスに移動する。

クエリを高々 $800000$ 回まで送ることで、AORイカちゃんが最初にいたマスを求めよ。

まず、地図の大きさを表す非負整数 $H, W$ と、地図を表す $H$ 行 $W$ 列の文字 $c_{i,j}$ が与えられる。

$H\ W$
$c_{0,0}, \dots , c_{0, W - 1}$
$\vdots$
$c_{H - 1, 0}, \dots , c_{H - 1, W - 1}$

続いて、あなたのプログラムは何回か応答プログラムに質問をする．質問のフォーマットは以下のとおりである。

? com

$com$ は U, D, L, R のうちいずれか $1$ 文字である。この質問で、指定された方向へ移動可能かを表す文字列が標準入力に $1$ 行で渡される。

何回か質問を行った後、あなたはAORイカちゃんの初期位置を当てる。AORイカちゃんが最初にいたマスを $c_{y,x}$ だとすると、

! y x

というフォーマットで出力する。初期位置を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。また、これら以外のフォーマットで出力した場合のジャッジ結果も不定である。

なお、質問や初期位置を応答プログラムに送ったあとフラッシュしないとTLEとなることがある。
フラッシュはCでは

fflush(stdout);

C++では

std::cout << endl;

で行うことができる。 fflush() は stdlib.h をインクルードすると使用できる。