ストーリー

あなたはロボットを遠隔操作してとある建物の内部構造を調査しようとしています。建物の内部にはいくつかの壁があって通行できません。
壁がある方向にロボットが進もうとした場合、ロボットはそこに壁があることをあなたに伝えて入口まで引き返します。
あなたの目的は、建物の入口から出口までの経路を発見することです。
ただしこのロボットには不具合があり、一定の確率で進行方向に壁がない場合でも壁があると判定してしまうことがわかっています。

問題文

縦$\ 20\$マス、横$\ 20\$マスのグリッドが与えられます。グリッドの外周は壁であり、隣接するマスとマスの間にも壁が存在することがあります。
一番左上のマスの座標を$(0, 0)$とし、そこから下に$\ i\$マス、右に$\ j\$マス進んだ先のマスの座標を$(i, j)$とします。この建物の入口はマス$(0, 0)$、出口はマス$(19, 19)$に位置します。
途中で壁を通行しないかつ最終到達地点が出口である経路を「目的の経路」と呼ぶことにします。
目的の経路を発見するまで、以下の試行を繰り返してください。各試行においてロボットは入口から移動を開始します。

• 上下左右の移動をそれぞれ U, D, L, R とし、移動経路を長さ$\ 400\$以下の文字列として出力してください。
• 出力された移動経路が目的の経路であった場合、ジャッジは$\ -1\$を返します。その場合は直ちにプログラムを終了してください。
• そうでない場合は、ロボットが移動できた回数が返されます。ただし、各移動において一定の確率$\ p\$で移動方向に壁がない場合でも移動に失敗して試行を終了します。
• $1001\$回目の試行においてジャッジは$\ -1\$を返すのでプログラムを直ちに終了してください。

得点

$t\$回目の試行において目的の経路を出力した場合、$1001-t\$の得点が得られます。ただし、試行回数が$\ 1001\$以上となった場合はそのテストケースにおける得点は$\ 0\$となります。
出力された文字列が U, D, L, R 以外の文字を含む場合は WA と判定されます。
テストケースは全部で$\ 100\$個あり、各テストケースの得点の合計が提出の得点となります。
コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われません。
コンテストの順位は上の「スコア順」タブよりご覧ください。

入力

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

$H\ W\ p$

$H\$はグリッドの行数、$W\$はグリッドの列数であり、全てのテストケースにおいて$\ H=W=20\$を満たします。
ロボットが移動に失敗する確率$\ p\$は百分率で与えられます。$p\$は$\ 6\$以上$\ 15\$以下の整数です。
全てのマスは入口から到達可能であることが保証されます。
また、各試行において文字列を出力後、一つの整数が標準入力から与えられます。
ジャッジの入力を必ず最後まで全て受け取ってください。行わなかった場合 WA となる可能性があります。

出力

各試行において、長さ$\ 400\$以下の文字列を一つ出力してください。出力された文字列の長さが$\ 400\$を超える場合、$401\$文字目以降は無視されます。
各出力の後に標準出力をflushしてください。そうしない場合 TLE となる可能性があります。
なお、ジャッジが$\ -1\$を返す前に提出プログラムが終了した場合およびジャッジが$\ -1\$を返した後に出力を行った場合の挙動は未定義です。

サンプル

5 5 10

DDDDRRRR

2

RRRRDDDD

3

RRRDDDDR

-1

入力生成方法

$L\$以上$\ U\$以下の整数値を一様ランダムに生成する関数を$\ rand(L,U)\$で表す。
$i\$番目のテストケースにおけるロボットが移動に失敗する確率を$\ p=6+(i-1) \% 10\$とする。
また、入力としては与えられないが、壁の位置は以下の手順で決定される。
初めに外周を除く壁の総数$\ M=rand(100,200)\$とし、以下の操作を$\ M\$回繰り返す。
ただし壁を設置した際に到達不可能なマスが発生する場合または既に壁が設置してある位置を選択した場合は設置せずに操作をやり直す。

• 壁の方向を決める乱数$\ D=rand(0,1)\$を生成する。
• $D=0\$の場合、$i=rand(0,19),j=rand(1,19)\$とし、マス$\ (i,j-1)\$とマス$\ (i,j)\$の間に壁を設置する。
• $D=1\$の場合、$i=rand(1,19),j=rand(0,19)\$とし、マス$\ (i-1,j)\$とマス$\ (i,j)\$の間に壁を設置する。

1. $1\$以上$\ 100\$以下の整数$\ c\$を一様ランダムに生成する。
2. $c\$を生成した回数が$\ 400 \$を超えた場合、$t_i=400\$として操作を終了する。
3. $c \leq p\$であれば操作を終了し、$t_i = (cを生成した回数) - 1\$とする。そうでなければ 1. に戻る。