Đây là phiên bản dễ 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à phiên bản khó là giới hạn số bước 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$, hàng $i$ có đúng một chướng ngại vật.
Với mọi $1\le j\le n$, cột $j$ có nhiều nhất một chướng ngại vật.
Ban đầu, Yuki ở ô $(1,1)$. Cô nghe nói 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ố bước di chuyển. Ở mỗi bước, 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 có chướng ngại vật, bước di chuyển đó không được thực hiện.
Đáng tiếc, 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 bước di chuyển sao cho với mọi cách bố trí chướng ngại vật hợp lệ, Yuki sẽ đến hàng $n+1$ vào một thời điểm nào đó (cô chỉ cần đến hàng $n+1$ ít nhất một lần; không cần ở lại đó sau khi thực hiện xong tất cả các bước).
Vì Yuki không vội, số bước di chuyển trong lời giải của bạn không được vượt quá $30\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\le30\cdot n$), biểu thị số bước 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 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 đi sang trái.
Nếu $s_i=\texttt{R}$, Yuki đi 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 thể hiện 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 dữ liệu ra 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 thể hiện 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, khi thực hiện các bước di chuyển được cho trong dữ liệu ra mẫu, Yuki sẽ đến hàng $n+1$.