これはこの問題の簡単版です。簡単版と難しい版の唯一の違いは、解答における移動回数の上限です。
Yuki は $n+1$ 行 $n$ 列のグリッド上に住んでいます。行には上から下へ $1$ から $n+1$、列には左から右へ $1$ から $n$ の番号が付いています。$(i,j)$ は $i$ 行 $j$ 列のマスを表します。
グリッド上には $n-1$ 個の障害物があり、その配置は次の条件を満たします。
$1$ 行目と $n+1$ 行目には障害物がありません。
すべての $2\le i\le n$ について、$i$ 行目には障害物がちょうど $1$ 個あります。
すべての $1\le j\le n$ について、$j$ 列目には障害物が高々 $1$ 個あります。
はじめ、Yuki は $(1,1)$ にいます。$n+1$ 行目にはカンガルーの群れが住んでいると聞いたので、景色を見るために $n+1$ 行目へ行きたいと考えています。
目標を達成するため、Yuki は何回か移動できます。各移動では、上下左右の四方向から一つを選び、その方向に $1$ マス移動します。ただし、移動先のマスがグリッドの外にあるか障害物を含む場合、その移動は実行されません。
残念ながら、Yuki は障害物の配置の規則しか知らず、障害物の具体的な位置は知りません。そこで、条件を満たすどのような障害物の配置でも、Yuki がいつか $n+1$ 行目に到達するような移動列を指定してほしいと考えています（$n+1$ 行目には少なくとも一度到達すればよく、すべての移動を終えた後もそこにいる必要はありません）。
Yuki は急いでいないので、解答における移動回数は $30\cdot n$ 以下でなければなりません。
入力
一行に正の整数 $n$（$2\le n\le 10^3$）が与えられます。
出力
一行目に、解答における移動回数を表す整数 $k$（$1\le k\le30\cdot n$）を出力してください。
二行目に長さ $k$ の文字列 $s$ を出力してください。$s_i$ は Yuki の $i$ 回目の移動の方向を表します。
$s_i=\texttt{U}$ の場合、Yuki は上に移動します。
$s_i=\texttt{D}$ の場合、Yuki は下に移動します。
$s_i=\texttt{L}$ の場合、Yuki は左に移動します。
$s_i=\texttt{R}$ の場合、Yuki は右に移動します。
入出力例
入力 1
2
出力 1
4 DRDD
入力 2
3
出力 2
17 DDDUUURDDDUUURDDD
注記
一つ目の例について：
- 灰色のマスを障害物、白色のマスを空きマスとします。次の図は、条件を満たす障害物の配置をすべて示しています。
一つ目の障害物の配置では、Yuki の経路は $(1,1)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$ です。
二つ目の障害物の配置では、Yuki の経路は $(1,1)\to(2,1)\to(2,1)\to(3,1)\to(3,1)$ です。
条件を満たすどの障害物の配置でも Yuki は $n+1$ 行目に到達するので、この出力例は正しいものです。
二つ目の例について：
- 灰色のマスを障害物、白色のマスを空きマスとします。次の図は、条件を満たす障害物の配置をすべて示しています。
- これらのどの障害物の配置でも、出力例に示された移動に従うと Yuki が $n+1$ 行目に到達することは容易に証明できます。