これはこの問題の難しいバージョンです。簡単なバージョンとの唯一の違いは、解答における移動回数の上限です。
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 \le j \le n$ に対して、第 $j$ 列には高々一つの障害物があります。
最初、Yuki は $(1, 1)$ にいます。第 $n + 1$ 行にカンガルーの群れが住んでいると聞いたので、第 $n + 1$ 行へ景色を見に行きたいと思っています。
目標を達成するため、Yuki は何回か移動できます。各移動では四つの方向（上、下、左、右）から一つを選び、その方向へ一マス移動します。ただし、移動先のマスがグリッドの外にあるか障害物を含む場合、その移動は実行されません。
残念ながら、Yuki が知っているのは障害物の配置規則だけで、具体的な位置は知りません。そこで、どのような条件を満たす障害物配置でも、Yuki がどこかの時点で第 $n + 1$ 行に到達するような移動列を指定してください（第 $n + 1$ 行には少なくとも一度到達すればよく、すべての移動が終わった後にそこにとどまる必要はありません）。
Yuki は急いでいるため、解答の移動回数は $10 \cdot n$ 以下でなければなりません。
入力
一行に正整数 $n$（$2 \le n \le 10^3$）が与えられます。
出力
一行目に、解答における移動回数を表す整数 $k$（$1 \le k \le 10 \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$ 行に到達することは容易に証明できます。