AT_codequeen2025_final_h ライブ

大人気アイドルグループである 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) $ に戻ってくるような経路のうち、ステージ間の移動回数が最小となる経路を一つ求めてください。

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

ステージ間の移動の最小回数を $ K $ として、以下で定義される長さ $ K $ の文字列 $ S $ を出力せよ。 - $ i $ 回目の移動前がステージ $ (r,c) $ 、移動後がステージ $ (r',c') $ だとすると、 $ S $ の $ i $ 文字目は以下のように定義される。 - $ r+1=r' $ のとき： $ S_i= $ `D` - $ r-1=r' $ のとき： $ S_i= $ `U` - $ c+1=c' $ のとき： $ S_i= $ `R` - $ c-1=c' $ のとき： $ S_i= $ `L`

### Sample Explanation 1 ライブステージは以下の画像のようになります。  例えばステージ $ (0,0) $ からスタートして以下の画像の通路に書かれた番号順に移動することで $ 8 $ 回の移動で全ての通路を通ることができます。  $ 8 $ 回未満の移動で全ての通路を通りステージ $ (0,0) $ に戻ることはできないので、 `RRDLUDLU` を出力すると正解となります。 また、`RRDLUDLU` のほかにも `RDRULDLU` などを出力しても正解となります。 ### Constraints - $ 1\le H ,W\le 100 $ - 入力される値は全て整数