AT_ahc033_a [AHC033A] Container Handling with Cranes

[problemUrl]: https://atcoder.jp/contests/ahc033/tasks/ahc033_a $ N\times\ N $ マスのコンテナターミナルがある。 一番左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 $ 0 $ から $ N^2-1 $ の番号が振られた $ N^2 $ 個のコンテナが運び込まれてくるので、$ N $ 台のクレーンを操作することで、指定された順番で搬出してほしい。 マップの左端と右端には、それぞれ以下のような搬入口・搬出口が存在する。 - 搬入口: 左端の各マスは搬入口であり、各搬入口からはコンテナがそれぞれ $ N $ 個ずつ順番に運び込まれてくる。事前にどの番号のコンテナが運び込まれて来るかが分かっており、$ (i,0) $ にある搬入口から $ j $ 番目に運び込まれるコンテナの番号は $ A_{i,j} $ である。 - 搬出口: 右端の各マスは搬出口であり、各搬出口に置かれたコンテナは即座に外部へ運び出される。$ (i,N-1) $ にある搬出口からは、$ N\times\ i,N\times\ i+1,\cdots,N\times\ i+N-1 $ 番のコンテナをこの順番で搬出したい。 搬入口、搬出口を含む各マスには高々 $ 1 $ つのコンテナを配置することが出来る。 搬出口以外に置かれたコンテナは搬出されないため、順番を調整するための一時置き場として利用出来る。 クレーンは $ 1 $ 台の大クレーンと、$ N-1 $ 台の小クレーンの $ 2 $ 種類が存在する。初期状態で大クレーンは $ (0,0) $ のマスに、小クレーンは $ (1,0),\ (2,0),\ \cdots,\ (N-1,0) $ の各マスに $ 1 $ 台ずつ配置されている。 各クレーンはコンテナを掴む、離す、隣接マスに移動する、といった操作が可能である。 コンテナが置かれていないマスには常にクレーンを移動可能であり、コンテナを掴んでいない場合はコンテナが置かれているマスにも移動出来る。 一方で、コンテナを掴んでいる状態でコンテナが置かれているマスに移動出来るかどうかは、クレーンの種類によって異なる。 大クレーンはコンテナを高く持ち上げて運ぶため、コンテナを掴んでいる状態でも他のコンテナが置かれているマスに移動することが出来る。 小クレーンの場合はコンテナを持ち上げる高さが低いため、コンテナを掴んでいる状態では他のコンテナが置かれているマスに移動することが出来ない。 毎ターン、各クレーンごとに独立に以下の操作から $ 1 $ つを選んで実行することが出来る。 - `P`: 現在位置に存在するコンテナを掴む。すでにコンテナを掴んでいる場合や、現在位置にコンテナが存在しない場合は WA となる。 - `Q`: 掴んでいるコンテナを離し、現在位置に配置する。コンテナを掴んでいない場合や、現在位置に既にコンテナが存在する場合は WA となる。 - `U`, `D`, `L`, `R`: 上下左右に隣接するマスへ移動する。小クレーンかつコンテナを掴んでいる状態の場合は、移動先のマスにコンテナが存在してはならない。$ N\times\ N $ マスの外へ移動するような操作を行うことは出来ない。 - `.`: 何もせずにその場に留まる。 - `B`: クレーンを爆破する。コンテナを掴んでいる状態では爆破することは出来ない。爆破したクレーンは盤面から排除され、以後 `.` 以外の操作をすることは出来ない。 禁止されている操作を行った場合、WA となる。 それぞれのクレーンはコンテナを掴んでいるかどうかに関わらず、重なったり、すれ違うことは出来ない。 すなわち、同じマスに複数のクレーンが存在してはならず、$ 2 $ つのクレーンがお互いの位置を交換するように移動することは出来ない。 各クレーンの操作は同時に行われるため、マス $ p $ に存在するクレーンがマス $ q $ に移動するのと同じターンに、マス $ q $ に存在するクレーンをマス $ r $ ($ r\neq\ p $) に移動させたり爆破したりするような操作が可能である。ただし、$ r=p $ の場合はすれ違う移動となるため不可能である。 各ターンは以下の $ 3 $ ステップからなる。 1. 運び込まれてくるコンテナがまだ残っている各搬入口について、そのマスにコンテナ及びコンテナを掴んだ状態のクレーンが存在しない場合、次の順番のコンテナがそのマスに配置される。 2. 各クレーンの操作を行う。 3. 各搬出口について、そのマスにコンテナが配置されている場合、そのコンテナを搬出して盤面から取り除く。 操作は最大で $ 10000 $ ターン繰り返すことが出来る。 短いターン数で指定された順番に近い順にコンテナを搬出出来るような操作列を求めてほしい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_{0,0} $ $ \cdots $ $ A_{0,N-1} $ $ \vdots $ $ A_{N-1,0} $ $ \cdots $ $ A_{N-1,N-1} $ - 全てのテストケースで $ N\ =\ 5 $ で固定である。 - $ A_{i,j} $ は $ (i,0) $ の搬入口から $ j $ 番目に搬入されるコンテナの番号であり、$ 0\leq\ A_{i,j}\leq\ N^2-1 $ を満たす整数値である。全ての $ A_{i,j} $ の値は異なる。

以下の形式で標準出力に出力せよ。 > $ S_0 $ $ \vdots $ $ S_{N-1} $ 各 $ S_i $ は `P`、`Q`、`U`、`D`、`L`、`R`、`.`、`B` のみからなる文字列であり、その $ t $ 文字目は初期位置 $ (i,0) $ のクレーンに対する $ t $ ターン目の操作を表す。 出力した各文字列の長さは $ 1 $ 以上 $ 10000 $ 以下でなければならない。 各文字列の長さは異なってもよく、その場合は最も長い文字列に合わせて文字列の末尾に `.` が追加される。 [例を見る](https://img.atcoder.jp/ahc033/ELSlXTEw.html?lang=ja&seed=0&output=sample)

### 得点 以下のように $ M_0,\ M_1,\ M_2,\ M_3 $ の値を定める。 - $ M_0 $: 出力した操作列のターン数。 - $ M_1 $: 正しい搬出口から搬出したコンテナの転倒数の総和。すなわち、$ (i,N-1) $ の搬出口から搬出されたコンテナのうち、番号 $ b $ が $ N\times\ i\leq\ b\