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

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 ไม่รีบร้อน จำนวนครั้งในการเคลื่อนที่ในคำตอบของคุณต้องไม่เกิน $30\cdot n$

ข้อมูลนำเข้า

มีเพียงบรรทัดเดียว ประกอบด้วยจำนวนเต็มบวก $n$ ($2\le n\le 10^3$)

ข้อมูลส่งออก

บรรทัดแรกให้พิมพ์จำนวนเต็ม $k$ ($1\le k\le30\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$