34166번 - 재우의 유수풀 서브태스크스페셜 저지

이제 재우는 수영에 통달했다. 수영대회를 여는 것에 만족하지 않은 재우는 워터파크를 개장하기로 했다.

재우는 워터파크에 유수풀을 건설해야 한다. 유수풀은 $N\times M$ 모양의 격자에서 건설되어야 하며, 편의상 격자의 가장 왼쪽 아래의 칸을 $\left( 1,1 \right)$, 가장 오른쪽 위의 칸을 $\left( N,M \right)$이라고 하자. $\left(x, y\right)$의 이웃한 칸은 다음 $4$개 칸들 중 격자 범위를 벗어나지 않는 칸들이다.

• 왼쪽 칸: $\left( x-1,y \right)$
• 오른쪽 칸: $\left( x+1,y \right)$
• 아래쪽 칸: $\left( x,y-1 \right)$
• 위쪽 칸: $\left( x,y+1 \right)$

모든 유수풀이 그렇듯 유수풀은 한 칸에서 출발해 이웃한 칸을 따라 이동 후 자신으로 돌아오는 사이클 모양이다. 이때 한 번 지난 칸을 다시 지나서는 안 되며, 출발칸으로 돌아와야 하며, 서로 다른 세 칸 이상을 지나야 한다. 출발칸 역시 처음과 마지막을 제외하고 중간에 지나서는 안 된다. 재우는 길이가 $K$인 유수풀을 만들고자 한다. 여기서 유수풀의 길이는, 유수풀이 지나는 서로 다른 칸의 개수를 의미한다.

출발칸은 마음대로 해도 되지만, 유수풀이 $N\times M$ 모양의 격자에서 벗어나면 안 될 때, 길이 $K$의 유수풀을 하나 찾아보자.

첫째 줄에 테스트 케이스의 개수 $T(1\leq T\leq 100)$가 주어진다.

각 테스트 케이스 별로 첫 번째 줄에 각각 직사각형 격자의 가로, 세로 길이를 의미하는 정수 $N,M(1\le N,M\le 100$; $2\le\max\left( N,M \right) )$과 사이클의 길이를 의미하는 정수 $K(1\le K\le N\cdot M)$가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄씩 길이가 $K$인 유수풀이 존재한다면, 아래와 같이 이를 의미하는 문자열로 출력한다. 만약 존재하지 않는다면 -1을 대신 출력하고, 가능한 유수풀이 여러 개라면 아무거나 출력해도 된다.

길이가 $K$인 유수풀은 길이가 $K$인 문자열로 표현되며, 아래와 같이 경로를 표현하면 된다.

• 위쪽으로 한 칸: U
• 아래쪽으로 한 칸: D
• 왼쪽으로 한 칸: L
• 오른쪽으로 한 칸: R

출발칸에서 출발해 다시 돌아와야 하며, 격자의 범위를 넘지 않아야 하고, 조건을 만족하는 사이클 모양이어야 한다.