呢個係本題嘅困難版本。簡單版本同困難版本唯一嘅分別，係你嘅方案入面移動次數嘅上限。
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$ 行。