H - ライブ Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550

問題文

大人気アイドルグループである Bit♡Beat はとても広い会場でライブをすることになりました。

ライブ会場は南北に H 行、東西に W 列のグリッドに区切られており、グリッドのしきりにあたる部分に通路があります。(詳しくは入出力例を参考にしてください。)

通路同士の交点にあたる場所にそれぞれ (H+1)(W+1) 個のステージがあり、最も北西にあるステージから南に r 本、東に c 本通路を進んだ先のステージをステージ (r,c) (0 \le r \le H , 0 \le c \le W) と表記します。

プロデューサーであるあなたは、アイドルがライブ中にステージ (0,0) から出発して全ての通路を 1 回以上通ってから再びステージ (0,0) に戻ってくるような経路を通るような経路を考えています。しかし、時間の都合上そのような経路のうちステージ間の移動回数が少ないようなものを採用したいと考えました。

(0,0) から出発して全ての通路を 1 回以上通ってから再びステージ (0,0) に戻ってくるような経路のうち、ステージ間の移動回数が最小となる経路を一つ求めてください。

制約

  • 1\le H ,W\le 100
  • 入力される値は全て整数

入力

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

H W

出力

ステージ間の移動の最小回数を K として、以下で定義される長さ K の文字列 S を出力せよ。

  • i 回目の移動前がステージ (r,c) 、移動後がステージ (r',c') だとすると、 Si 文字目は以下のように定義される。
    • r+1=r' のとき: S_i= D
    • r-1=r' のとき: S_i= U
    • c+1=c' のとき: S_i= R
    • c-1=c' のとき: S_i= L

入力例 1

1 2

出力例 1

RRDLUDLU

ライブステージは以下の画像のようになります。

例えばステージ (0,0) からスタートして以下の画像の通路に書かれた番号順に移動することで 8 回の移動で全ての通路を通ることができます。

8 回未満の移動で全ての通路を通りステージ (0,0) に戻ることはできないので、 RRDLUDLU を出力すると正解となります。

また、RRDLUDLU のほかにも RDRULDLU などを出力しても正解となります。


入力例 2

1 1

出力例 2

DRUL

入力例 3

2 2

出力例 3

DDRUURDDLURLLURL