A - Polish and Slide Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

N\times N のマスからなる盤面がある。 左上のマスの座標を (0,0) とし、そこから下に i マス、右に j マス進んだ位置のマスの座標を (i,j) とする。

あなたは初期位置 (i_0, j_0) におり、指定された目的地 (i_1, j_1), \dots, (i_{M-1}, j_{M-1}) をこの順番で訪れたい。

各ターンでは、以下のいずれかの行動を 1 つ選んで実行できる。

  • 磨く: 現在位置のマスをピカピカに磨き上げる。初期状態ではどのマスも磨かれていない。既に磨いたマスに対してこの操作を行っても何も変化しない。
  • 滑る: 上下左右の方向 d を指定し、盤面外に出ようとするか、磨かれていないマスに到達するまで、その方向への移動を繰り返す。より詳細には、以下の繰り返しを行う。
    1. d 方向に隣接するマスが盤面外である場合、その場にとどまり繰り返しを終了する。
    2. d 方向に隣接するマスが磨かれていない場合、隣接マスに移動して繰り返しを終了する。
    3. d 方向に隣接するマスが磨かれている場合、隣接マスに移動して繰り返す。

example

「滑る」による移動中に、次に訪れるべき目的地のマスに到達した、または通過した場合、その時点でその目的地を訪れたものとみなす。同じ「滑る」の移動中に複数の目的地を指定された順番通りに通過した場合、それらはすべて訪れたものとみなされる。 一方、まだ訪れる順番ではない目的地のマスに到達した、または通過しても、その時点では訪れたものとはみなされない。その目的地を訪れる順番になった後に、改めてそのマスに到達するか通過する必要がある。

行動は最大で 10000 ターンまで行える。 できるだけ少ないターン数ですべての目的地を順に訪れるような行動列を求めよ。

得点

出力した行動列のターン数を T としたとき、10000-T の得点を得る。

すべての目的地を順に訪れることができなかった場合、WA となる。

テストケースは全部で 100 個あり、各テストケースの得点の合計が提出の得点となる。 1 つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA または TLE となる。

入力

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

N M
i_0 j_0
\vdots
i_{M-1} j_{M-1}
  • すべてのテストケースにおいて、N=20、M=100 で固定されている。
  • 初期位置および目的地の座標 (i_k,j_k) は、0 \leq i_k, j_k \leq N-1 を満たす整数であり、すべて互いに異なる。

出力

各ターンの行動を、以下のようにアルファベット 1 文字で表す。

  • 磨く: P
  • 滑る: 滑る方向に応じて、上：U、下：D、左：L、右：R

ターン数を T、t ターン目の行動を表す文字を a_t としたとき、以下の形式で標準出力に出力せよ。

a_0
\vdots
a_{T-1}

例を見る

入力生成方法

初期位置および目的地は、以下の手順に従って生成される。

まず、すべての N^2 個のマスの座標をランダムな順序に並び替える。 並び替えた座標列のうち、先頭から M 個を順に (i_0,j_0), (i_1,j_1), \dots, (i_{M-1},j_{M-1}) として採用する。

ツール(入力ジェネレータ・ビジュアライザ)

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