問題文

$N × N$ のマス目の中に、$M$ 台のロボットと、$B$ 個のブロックマス、$1$ 個のゴールマスがあります。

各マスは座標を持ち、左上隅のマスの座標は $(0, 0)$、右上隅のマスの座標は $(0, N - 1)$、右下隅のマスの座標は $(N - 1, N - 1)$ です。このマス目の左端と右端、上端と下端はそれぞれ繋がっており、例えばマス $(3, 0)$ の左隣のマスは $(3, N - 1)$、マス $(N - 1, 5)$ の真下のマスは $(0, 5)$ です。

各ロボット $i$ ($1 \\leq i \\leq M$) について、初期位置 $(ry_i, rx_i)$ と向きの初期値 $c_i$ が与えられます。$c_i$ は U, D, L, R のいずれかであり、それぞれ上下左右を表します。

また、各ブロックマスやゴールマスの座標も与えられます。$i$ 個目のブロックマス ($1 \\leq i \\leq B$) の座標は $(by_i, bx_i)$、ゴールマスの座標は $(gy, gx)$ です。

あなたは、何個かのマスを選んでそれらに 方向案内 を設置することができます。それぞれの方向案内には、上下左右いずれかの向きを指定します。$1$ 個のマスに複数の方向案内を設置することはできません。

方向案内の設置が完了したあと、各ロボットはそれぞれ個別に以下の動作を繰り返します。ロボット同士が衝突することはありません。

• ゴールマスにいる場合: その場で停止する。
• そうでない場合: まず、現在いるマスに方向案内が設置されていれば、自分の向きを指定された向きに変える。その後、自分が向いている方向に $1$ マス移動する (マス目の左端と右端、上端と下端がそれぞれ繋がっていることに注意せよ)。ただし、移動先がブロックマスである場合は移動に失敗し、その場で停止する。

有限回の動作でゴールマスに到達できるロボットの数をできるだけ多くしてください。使用する方向案内の数が少なく、ロボットが通るマスが多いとさらに高得点となります。より詳しくは「出力」セクションをご確認ください。

【注意】この問題では、「最適解」を求める必要はありません。例えば、全てのロボットをゴールさせたり、方向案内の個数を最小化する必要はありません。

制約

• $N = 40$
• $M = 100$
• $B = 300$
• $0 ≦ gy, gx ≦ N - 1$
• $0 ≦ ry_i, rx_i ≦ N - 1$
• $c_i$ は U, D, L, R のいずれかである。
• $0 ≦ by_i, bx_i ≦ N - 1$
• ブロックマスは、ロボット・ゴールマス・他のブロックマスのいずれとも重ならない。(ロボット同士や、ロボットとゴールマスは重なることがある)
• 以上の制約を満たす範囲で、ブロックマス、ゴールマス、ロボットの存在するマスは一様ランダムに選ばれる。

入力

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

$N$ $M$ $B$ $gy$ $gx$ $ry_1$ $rx_1$ $c_1$ $ry_2$ $rx_2$ $c_2$ $:$ $ry_M$ $rx_M$ $c_M$ $by_1$ $bx_1$ $by_2$ $bx_2$ $:$ $by_B$ $bx_B$

出力

設置する方向案内の個数を $K$、$i$ 個目の方向案内を設置する座標を $(Y_i, X_i)$、$i$ 番目の方向案内に指定する向きを $R_i$ (U, D, L, R のいずれかであり、それぞれ上下左右に対応) として、以下のフォーマットで出力せよ。

$K$ $Y_{1}$ $X_{1}$ $R_1$ $Y_{2}$ $X_{2}$ $R_2$ $:$ $Y_{K}$ $X_{K}$ $R_K$

上記のフォーマットを満たさない場合は「不正解」となることがある。例えば、文字列の個数が一致しない場合や、指定された文字以外が使用された場合である。

また、同一のマスに複数の方向案内を設置しても不正解となる。ただし、ゴールマスやブロックマスに方向案内を設置しても不正解とはならない。

テストケースは $50$ 個与えられる。各テストケースについて、有限回の動作でゴールマスに到達できるロボットの数を $A$、設置した方向案内の数を $B$、ロボットが一度でも通るマスの数を $C$ とすると、そのテストケースでは $1000 \\times A - 10 \\times B + C$ 点が得られる。 全てのテストケースにおける合計点が、その提出の得点となる。

不正解となる出力が行われた場合は、そのテストケースが入力例として与えられているものであれば、そのテストケースでの得点が $0$ 点となる。その他のテストケースであれば、入力例以外の全てのテストケースでの得点が $0$ 点となる。

入出力例

入力例および出力例は このリンク からダウンロードできます。