Đây là phiên bản khó của bài toán này. Điểm khác biệt duy nhất giữa phiên bản dễ và khó là giới hạn số lần di chuyển trong lời giải của bạn.
Yuki sống trên một lưới có $n + 1$ hàng và $n$ cột. Các hàng được đánh số từ $1$ đến $n + 1$ từ trên xuống dưới, còn các cột được đánh số từ $1$ đến $n$ từ trái sang phải. Gọi $(i, j)$ là ô ở hàng $i$, cột $j$.
Có $n - 1$ chướng ngại vật trên lưới, và cách bố trí của chúng thỏa mãn các điều kiện sau:
Không có chướng ngại vật ở hàng $1$ và hàng $n + 1$.
Với mọi $2 \le i \le n$, có đúng một chướng ngại vật ở hàng $i$.
Với mọi $1 \le j \le n$, có nhiều nhất một chướng ngại vật ở cột $j$.
Ban đầu, Yuki ở $(1, 1)$. Cô nghe nói có một đàn kangaroo sống ở hàng $n + 1$, nên muốn đến hàng $n + 1$ để ngắm cảnh.
Để đạt được mục tiêu, Yuki có thể thực hiện một số lần di chuyển. Trong mỗi lần, cô chọn một trong bốn hướng (lên, xuống, trái, phải) và di chuyển một ô theo hướng đó. Cụ thể, nếu ô đích nằm ngoài lưới hoặc chứa chướng ngại vật, lần di chuyển đó không được thực hiện.
Tiếc là Yuki chỉ biết các quy tắc bố trí chướng ngại vật, chứ không biết vị trí cụ thể của chúng. Vì vậy, cô muốn bạn giúp xác định một dãy di chuyển sao cho với mọi cách bố trí chướng ngại vật hợp lệ, Yuki đều đến được hàng $n + 1$ tại một thời điểm nào đó (cô chỉ cần từng đến hàng $n + 1$ ít nhất một lần; không cần ở lại đó sau khi hoàn thành tất cả các lần di chuyển).
Vì Yuki đang vội, số lần di chuyển trong lời giải của bạn không được vượt quá $10 \cdot n$.
Dữ liệu vào
Một dòng duy nhất chứa số nguyên dương $n$ ($2 \le n \le 10^3$).
Dữ liệu ra
Dòng đầu tiên in ra số nguyên $k$ ($1 \le k \le 10 \cdot n$), biểu thị số lần di chuyển trong lời giải của bạn.
Dòng thứ hai in ra xâu $s$ có độ dài $k$, trong đó $s_i$ biểu thị hướng di chuyển lần thứ $i$ của Yuki:
Nếu $s_i = \texttt{U}$, Yuki đi lên.
Nếu $s_i = \texttt{D}$, Yuki đi xuống.
Nếu $s_i = \texttt{L}$, Yuki sang trái.
Nếu $s_i = \texttt{R}$, Yuki sang phải.
Ví dụ
Dữ liệu vào 1
2
Dữ liệu ra 1
4 DRDD
Dữ liệu vào 2
3
Dữ liệu ra 2
17 DDDUUURDDDUUURDDD
Ghi chú
Với ví dụ thứ nhất:
- Các ô màu xám biểu thị chướng ngại vật và các ô màu trắng biểu thị ô trống. Hình sau cho thấy tất cả các cách bố trí chướng ngại vật có thể có thỏa mãn yêu cầu:
Với cách bố trí chướng ngại vật thứ nhất, đường đi của Yuki là $(1, 1) \to (1, 1) \to (1, 2) \to (2, 2) \to (3, 2)$.
Với cách bố trí chướng ngại vật thứ hai, đường đi của Yuki là $(1, 1) \to (2, 1) \to (2, 1) \to (3, 1) \to (3, 1)$.
Với mỗi cách bố trí chướng ngại vật hợp lệ, Yuki đều đến hàng $n + 1$, nên kết quả mẫu là đúng.
Với ví dụ thứ hai:
- Các ô màu xám biểu thị chướng ngại vật và các ô màu trắng biểu thị ô trống. Hình sau cho thấy tất cả các cách bố trí chướng ngại vật có thể có thỏa mãn yêu cầu:
- Dễ chứng minh rằng với bất kỳ cách bố trí chướng ngại vật nào trong số này, thực hiện các lần di chuyển được đưa ra trong kết quả mẫu sẽ đưa Yuki đến hàng $n + 1$.