AT_ahc066_a [AHC066A] Macro Controller

AtCoder 社の高橋社長は球技が好きである。 しかし、仕事の合間にさまざまなボールで遊んでいるうちに、オフィス中にボールを散らかしてしまった。 それを見た青木副社長は大変怒り、高橋社長にすぐ片付けるよう命じた。 困った高橋社長は、最近購入したお片付けロボットを使ってボールを片付けることにした。 このロボットは、前進・右折・左折・交換という基本操作によって、オフィス内を移動しながらボールを拾ったり置いたりできる。 さらに、付属のコントローラーにはマクロ機能があり、一連の操作を記録して後から再生することもできる。 高橋社長の代わりに、できるだけ短い操作列で、すべてのボールを対応するかごに片付けてほしい。

$ N\times N $ マスの盤面がある。 左上のマスの座標を $ (0,0) $ とし、下方向に $ i $ 、右方向に $ j $ 進んだ位置の座標を $ (i,j) $ とする。 盤面の外周は壁で囲まれており、隣接するマス間にも壁が存在する場合がある。 すべてのマスは、壁を越えずに上下左右の移動を繰り返すことで互いに到達可能であることが保証されている。 盤面上には、 $ M $ 種類のボールと、 $ M $ 種類のかごが置かれている。 各種類 $ k\ (0\leq k

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ T $ $ v_0 $ $ \vdots $ $ v_{N-1} $ $ h_0 $ $ \vdots $ $ h_{N-2} $ $ b_0 $ $ c_0 $ $ d_0 $ $ e_0 $ $ \vdots $ $ b_{M-1} $ $ c_{M-1} $ $ d_{M-1} $ $ e_{M-1} $ ここで、 $ (b_k,c_k) $ は種類 $ k $ のボールの初期位置を表し、 $ (d_k,e_k) $ は種類 $ k $ のかごの位置を表す。 各値は以下の制約を満たす。 - $ 10\leq N\leq 20 $ - $ N/2\leq M\leq 2N $ - $ 1\leq T\leq 2N^2 M $ - $ v_{i,0} \cdots v_{i,N-2} $ は長さ $ N-1 $ の `01` からなる文字列であり、 $ j $ 文字目 $ v_{i,j} $ はマス $ (i, j) $ とマス $ (i, j+1) $ の間に壁がある（`1`）かない（`0`）かを表す。 - $ h_{i,0} \cdots h_{i,N-1} $ は長さ $ N $ の `01` からなる文字列であり、 $ j $ 文字目 $ h_{i,j} $ はマス $ (i, j) $ とマス $ (i+1, j) $ の間に壁がある（`1`）かない（`0`）かを表す。 - すべてのマスは互いに到達可能であることが保証されている。 - ボールの初期位置とかごの位置はすべて相異なる。

操作列の長さを $ A $ 、 $ t $ 回目の操作を表す文字 (`F`, `R`, `L`, `S`, `M`, `P`) を $ a_t $ としたとき、以下の形式で標準出力に出力せよ。 > $ a_0 $ $ \vdots $ $ a_{A-1} $ 出力する操作列の長さ $ A $ は $ T $ 以下でなければならない。 [例を見る](https://img.atcoder.jp/ahc066/O25rQjiK.html?lang=ja&seed=0&output=sample)

### 得点 出力した操作列の長さを $ A $ とする。 ここで、`M` および `P` もそれぞれ 1 回のボタン操作として数える。 シミュレーション終了時に、対応するかごのマスに置かれているボールの個数を $ V $ とする。 このとき、各テストケースに対して以下の絶対スコアが得られる。 - $ V=M $ の場合、 $ A $ - $ V