นี่คือฉบับยากของโจทย์นี้ ความแตกต่างเพียงอย่างเดียวระหว่างฉบับง่ายและฉบับยากคือข้อจำกัดจำนวนครั้งในการเคลื่อนที่ในคำตอบของคุณ

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$) ซึ่งแทนจำนวนครั้งในการเคลื่อนที่ในคำตอบของคุณ

บรรทัดที่สองให้พิมพ์สตริง $s$ ความยาว $k$ โดย $s_i$ แทนทิศทางการเคลื่อนที่ครั้งที่ $i$ ของ Yuki:

• ถ้า $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$