Magic Path

$N\times M$ 격자의 각 칸에는 사람이 살거나 살지 않는다. 행은 위에서 아래로 $0,1,\cdots,N-1$, 열은 왼쪽에서 오른쪽으로 $0,1,\cdots,M-1$의 번호가 붙어 있다. 격자점의 좌표는 $(i,j)$로 나타내며, $0\le i\le N$, $0\le j\le M$이다.

$(0,0)$에서 $(N,M)$까지 격자선을 따라 이동하는 경로를 하나 출력해야 한다. 한 번의 이동으로 상하좌우로 인접한 격자점으로 이동할 수 있으며, 격자 밖으로 나갈 수 없다.

사람이 사는 각 칸에 대하여, 그 칸을 이루는 네 꼭짓점 중 하나 이상을 경로가 방문했다면 그 칸에서 비용 $1$이 발생한다. 한 칸의 꼭짓점을 여러 번 방문해도 그 칸의 비용은 한 번만 계산한다. 경로의 비용은 비용이 발생한 칸의 수이다.

구체적인 점수 계산 방식은 Scoring 섹션을 참고한다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 다음 두 줄을 출력한다.

$C\ K$ $S$

$S$는 길이가 $K$인 문자열이며, 각 문자는 U, D, L, R 중 하나이다. 각각 현재 격자점에서 위, 아래, 왼쪽, 오른쪽으로 한 칸 이동함을 뜻한다.

$S$가 나타내는 이동은 에서 시작하여 항상 격자 안에 있어야 하고, 마지막에는 에 도착해야 한다.

• $1\le T\le 100\,000$.
• $1\le N,M\le 1\,000$.
• 모든 테스트 케이스에 대한 의 합은 이하이다.

이 문제의 채점은 각 서브태스크별로 독립적으로 이루어지며, 아래의 근사비 기준은 모든 서브태스크에 동일하게 적용된다.

각 테스트 케이스의 최적 비용을 $o$, 참가자가 출력한 유효한 경로의 실제 비용을 $a$라고 하자. 다음과 같이 근사비 $c$를 정의한다.