题目描述

这是本题的简单版本。简单版本和困难版本的唯一区别在于你给出的方案的移动次数限制。

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 仍位于第 $n + 1$ 行）。

由于 Yuki 没那么着急，你给出的方案的移动次数不能大于 $\boldsymbol{30 \cdot n}$。

输入格式

共一行，包含一个正整数 $n$ $(2 \le n \le 10^3)$。

输出格式

第一行，输出一个整数 $k$ $(1 \le k \le 30 \cdot n)$，表示你给出的方案的移动次数。

第二行，输出一个长度为 $k$ 的字符串 $s$，其中 $s_i$ 表示第 $i$ 次移动中 Yuki 的移动方向：

• 若 $s_i = \texttt U$，则表示第 $i$ 次移动中 Yuki 的移动方向为向上。
• 若 $s_i = \texttt D$，则表示第 $i$ 次移动中 Yuki 的移动方向为向下。
• 若 $s_i = \texttt L$，则表示第 $i$ 次移动中 Yuki 的移动方向为向左。
• 若 $s_i = \texttt R$，则表示第 $i$ 次移动中 Yuki 的移动方向为向右。

2

4
DRDD

3

17
DDDUUURDDDUUURDDD

提示

对于第 $1$ 组样例：

• 设灰色格子表示有障碍的格子，白色格子表示没有障碍的格子，则下图给出了所有满足要求的障碍分布方式： :::align{center} :::
• 对于第 $1$ 种障碍分布方式，Yuki 的移动路径为 $(1,1) \to (1,1) \to (1,2) \to (2,2) \to (3,2)$。
• 对于第 $2$ 种障碍分布方式，Yuki 的移动路径为 $(1,1) \to (2,1) \to (2,1) \to (3,1) \to (3,1)$。
• 对于每种满足要求的障碍分布方式，Yuki 都到达过棋盘的第 $n + 1$ 行，因此样例输出正确。

对于第 $2$ 组样例：

• 设灰色格子表示有障碍的格子，白色格子表示没有障碍的格子，则下图给出了所有满足要求的障碍分布方式： :::align{center} :::
• 容易证明，对于其中任意一种障碍分布方式，按照样例输出中给出的移动方式移动，Yuki 都到达过棋盘的第 $n + 1$ 行。