34180번 - 재우의 워터슬라이드 서브태스크스페셜 저지

문제

본인의 워터파크에 유수풀 설치를 완료한 재우는 이제 워터슬라이드도 만들고자 한다.

워터슬라이드는 $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) ),ドル 출발칸 $\left( x_s,y_s \right)$과 도착칸 $\left( x_f,y_f \right)$을 의미하는 네 정수 $x_s,y_s,x_f,y_f(1\le x_s,x_f\le N$; 1ドル\le y_s,y_f\le M$; $\left( x_s,y_s \right)\ne\left( x_f,y_f \right) ),ドル 워터슬라이드의 길이를 의미하는 정수 $K(1\le K\le N\cdot M)$가 공백으로 구분되어 주어진다.

출력

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

길이가 $K$인 워터슬라이드는 길이가 $K-1$인 문자열로 표현되며, 아래와 같이 경로를 표현하면 된다.

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

출발칸에서 출발해 도착칸에 도착해야 하며, 격자의 범위를 넘지 않아야 하고, 조건을 만족하는 경로여야 한다.

제한

서브태스크

힌트