Ini adalah versi sulit dari soal ini. Satu-satunya perbedaan antara versi mudah dan sulit adalah batas jumlah gerakan dalam solusi Anda.

Yuki tinggal pada sebuah petak dengan $n + 1$ baris dan $n$ kolom. Baris diberi nomor $1$ hingga $n + 1$ dari atas ke bawah, dan kolom diberi nomor $1$ hingga $n$ dari kiri ke kanan. Misalkan $(i, j)$ menyatakan sel pada baris $i$ dan kolom $j$.

Terdapat $n - 1$ rintangan pada petak, dan penempatannya memenuhi kondisi berikut:

• Tidak ada rintangan pada baris $1$ dan baris $n + 1$.

• Untuk setiap $2 \le i \le n$, terdapat tepat satu rintangan pada baris $i$.

• Untuk setiap $1 \le j \le n$, terdapat paling banyak satu rintangan pada kolom $j$.

Awalnya, Yuki berada di $(1, 1)$. Ia mendengar bahwa sekelompok kanguru tinggal di baris $n + 1$, sehingga ia ingin pergi ke baris $n + 1$ untuk melihat pemandangan.

Untuk mencapai tujuannya, Yuki dapat melakukan beberapa gerakan. Pada setiap gerakan, ia memilih salah satu dari empat arah (atas, bawah, kiri, kanan) dan berpindah satu sel ke arah tersebut. Secara khusus, jika sel tujuan berada di luar petak atau berisi rintangan, gerakan itu tidak dilakukan.

Sayangnya, Yuki hanya mengetahui aturan penempatan rintangan, bukan lokasi tepatnya. Oleh karena itu, ia ingin Anda membantunya menentukan urutan gerakan sedemikian sehingga untuk setiap penempatan rintangan yang valid, Yuki mencapai baris $n + 1$ pada suatu saat (ia hanya perlu pernah mencapai baris $n + 1$ setidaknya sekali; ia tidak harus tetap di sana setelah semua gerakan selesai).

Karena Yuki sedang terburu-buru, jumlah gerakan dalam solusi Anda tidak boleh melebihi $10 \cdot n$.

Masukan

Satu baris berisi sebuah bilangan bulat positif $n$ ($2 \le n \le 10^3$).

Keluaran

Pada baris pertama, cetak sebuah bilangan bulat $k$ ($1 \le k \le 10 \cdot n$), yang menyatakan jumlah gerakan dalam solusi Anda.

Pada baris kedua, cetak sebuah string $s$ sepanjang $k$, dengan $s_i$ menyatakan arah gerakan Yuki yang ke-$i$:

• Jika $s_i = \texttt{U}$, Yuki bergerak ke atas.

• Jika $s_i = \texttt{D}$, Yuki bergerak ke bawah.

• Jika $s_i = \texttt{L}$, Yuki bergerak ke kiri.

• Jika $s_i = \texttt{R}$, Yuki bergerak ke kanan.

Contoh

Masukan 1

2

Keluaran 1

4
DRDD

Masukan 2

3

Keluaran 2

17
DDDUUURDDDUUURDDD

Catatan

Untuk contoh pertama:

• Sel abu-abu menyatakan rintangan dan sel putih menyatakan sel kosong. Gambar berikut menunjukkan semua kemungkinan penempatan rintangan yang memenuhi persyaratan:

• Untuk penempatan rintangan pertama, jalur Yuki adalah $(1, 1) \to (1, 1) \to (1, 2) \to (2, 2) \to (3, 2)$.

• Untuk penempatan rintangan kedua, jalur Yuki adalah $(1, 1) \to (2, 1) \to (2, 1) \to (3, 1) \to (3, 1)$.

• Untuk setiap penempatan rintangan yang valid, Yuki mencapai baris $n + 1$, sehingga keluaran contoh tersebut benar.

Untuk contoh kedua:

• Sel abu-abu menyatakan rintangan dan sel putih menyatakan sel kosong. Gambar berikut menunjukkan semua kemungkinan penempatan rintangan yang memenuhi persyaratan:

• Mudah dibuktikan bahwa untuk setiap penempatan rintangan ini, dengan mengikuti gerakan yang diberikan dalam keluaran contoh, Yuki akan mencapai baris $n + 1$.