這是本題的困難版本。簡單版本與困難版本唯一的差別是解答中移動次數的限制。
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$ 列。