이 문제는 쉬운 버전입니다. 쉬운 버전과 어려운 버전의 유일한 차이점은 해답에서 허용되는 이동 횟수의 제한입니다.
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는 장애물 배치의 규칙만 알고 있을 뿐, 장애물의 구체적인 위치는 알지 못합니다. 따라서 그녀는 어떤 유효한 장애물 배치에 대해서도 어느 시점에는 반드시 $n+1$번째 행에 도달하도록 하는 이동 순서를 당신이 정해주기를 원합니다 ($n+1$번째 행에 최소 한 번 도달하기만 하면 되며, 모든 이동이 끝난 후에도 그곳에 머물러 있을 필요는 없습니다).
Yuki는 급하지 않기 때문에, 당신의 해답에서 이동 횟수는 $30\cdot n$을 초과해서는 안 됩니다.
입력
한 줄에 양의 정수 $n$ ($2\le n\le 10^3$)이 주어집니다.
출력
첫 번째 줄에는 당신의 해답에서의 이동 횟수를 나타내는 정수 $k$ ($1\le k\le30\cdot n$)를 출력합니다.
두 번째 줄에는 길이 $k$인 문자열 $s$를 출력하며, 여기서 $s_i$는 Yuki의 $i$번째 이동 방향을 나타냅니다:
$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$번째 행에 도달함을 쉽게 증명할 수 있습니다.