問題文

床マスと壁マスで構成された $H \times W$ のグリッドからなる迷路があります。あなたはロボットを使ってこの迷路を探査しようとしています。

あなたは最初にグリッド上の床マスを $1$ つ選んでそこにロボットを置くことができます。また、その際のロボットの向きについても上下左右の四方向から選べます。

その後、あなたはロボットに次の $2$ 種類の指示を好きな回数繰り返し出すことができます。

• 直進：ロボットが向いている方向に $1$ マス進む
• 右折：ロボットの向きを時計回りに $90$ 度変えた後、向いている方向に $1$ マス進む

どちらの指示を選んでも必ず $1$ マス進むことに注意してください。

あなたの目的は、ロボットに全ての床マスを通らせる事です（最初や最後にロボットが居るマスも通ったものとします）。壁マスに立ち入ることはできません。

しかし、ロボットが同じ床マスを $2$ 回以上通ると、迷路の床が崩れ、ロボットは壊れてしまいます。また、移動先が壁マスまたはグリッドの外側である場合も、ロボットは壊れてしまいます。

ロボットを壊さずに、目的を達成することは可能でしょうか？可能であれば、それを実現するロボットの初期状態と指示の列の一例を求めてください。

目的の達成が不可能な場合は -1 を出力してください。

制約

• $1 \leq H, W \leq 2000$
• $S_i$ は . および # のみからなる長さ $W$ の文字列
• 少なくとも $1$ つ床マスが存在する

入力

入力は以下の形式で標準入力から与えられる。

$H\ W$
$S_1$
$S_2$
$\vdots$
$S_H$

$S_i$ の $j$ 文字目が . のとき迷路の上から $i$ 行目、左から $j$ 列目のマスは床マス、# のとき壁マスである。

出力

ロボットを壊さずに目的を達成できるロボットの初期状態と指示の列の一例を、以下の形式で出力してください。存在しない場合は -1 を出力してください。

$r\ c\ d$
$t$
$X$

ただし、各変数の意味は以下の通りです。

• $r$ はロボットを初めに置くマスがグリッドの上から何行目かを表す、$1$ 以上 $H$ 以下の整数
• $c$ はロボットを初めに置くマスがグリッドの左から何列目かを表す、$1$ 以上 $W$ 以下の整数
• $d$ はロボットを初めに置く向きを表す文字であり、U は上、R は右、D は下、L は左を表す
• $t$ はロボットに与える指示の回数を表す、$0$ 以上 $HW-1$ 以下の整数
• $X$ はロボットに与える指示の列を表す長さ $t$ の文字列であり、$i$ 回目の指示が「直進」である場合 $X$ の $i$ 文字目は F、「右折」である場合 R である

最後に改行してください。

ビジュアライザ

出力結果のWeb版ビジュアライザがこちらで提供されています。

コンテスト中における、ビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。

また、ビジュアライザの仕様に関する質問は原則受け付けません。あくまで補助ツールとしてご利用ください。

サンプル

サンプル1

入力

3 4
....
..#.
#...

出力

2 2 L
9
FRRFFRFRF

上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表記します。

ロボットは最初 $(2, 2)$ に左を向いて置かれ、以下の経路で全ての床マスを通ります。

$(2, 2) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 3) \rightarrow (3, 2)$

2 3
#..
..#

-1