The Unstoppable Robot

迷路を移動できるロボットを開発している学生たちがいました。しかし、このロボットには欠点があり、いったん動き始めると、壁や障害物にぶつかるまで方向転換や停止ができません。そのため、ロボットが動き始めると、今向いている方向の一番近い壁に到達してから、次の進む方向を選ぶ必要があります。

このロボットが、スタート位置の S からゴール位置の E まで移動する際に必要な最小の移動回数を求め、そのために送信するコマンド列を出力してください。コマンドは以下のとおりです:

• L - 左に進む

• U - 上に進む

• R - 右に進む

• D - 下に進む

Input

入力の最初の行には、グリッドの高さと幅を表す 2 つの数値 h と w (2 ≤ h, w ≤ 100) が与えられます。

続く h 行には、幅 w 文字で構成されるグリッドが与えられます:

• . は床を表します

• # は壁を表します

• S はスタート地点を表します

• E はゴール地点を表します

また、ロボットがグリッドの外に出ないよう、周囲がすべて壁で囲まれていることが保証されています。

Output

プログラムは、スタート地点からゴール地点に到達するまでに必要な最小の移動回数を、最初の行に出力します。続く行には、ロボットに送るコマンド列を出力してください。可能な解答が複数ある場合は、いずれかを出力すれば構いません。

もしゴール地点まで到達できない場合は、Impossible と出力してください。

Examples

Input

7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########

Output

4
RDLU