최단 경로가 아닌 경로

이 문제에서는 $4 \times 4$ 격자판의 한쪽 모서리에서 반대쪽 모서리까지, 최단 경로가 아닌 단순 경로를 따라 이동해야 한다.

평면 위에 $4 \times 4$ 칸으로 이루어진 격자판이 있다. 각 칸은 비어 있거나 벽으로 완전히 막혀 있다.

로봇 아우렐리우스는 이 격자판에서 여러 문제를 풀어 지능 수준을 측정하는 시험을 치르고 있다. 그는 이미 임의의 경로를 찾는 문제와 두 칸 사이의 최단 경로를 찾는 문제를 해결했다.

이번 과제에서 아우렐리우스는 빈 칸만 지나며 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 걸어가야 한다. 한 걸음은 현재 칸과 변을 공유하는 다른 칸으로 옮기는 것이다. 경로는 단순해야 하므로, 같은 칸을 두 번 이상 방문할 수 없다. 또한 경로의 길이는 이 격자판에서 두 모서리 사이 최단 경로의 길이보다 반드시 길어야 한다. 경로의 길이는 이동 횟수다.

아우렐리우스가 이 과제를 마치도록 돕는 프로그램을 작성하라.

입력에는 테스트 케이스가 하나 이상 주어진다. 각 테스트 케이스는 네 줄로 주어지며, 각 줄은 격자판의 한 행을 나타내고 정확히 네 글자로 이루어져 있다. 빈 칸은 .(점, ASCII 46)으로, 벽은 #(샵, ASCII 35)으로 나타낸다. 연속된 테스트 케이스는 - 네 개(하이픈, ASCII 45)만으로 이루어진 줄로 구분한다.

왼쪽 위 칸과 오른쪽 아래 칸은 항상 비어 있다. 또한 한 입력에 있는 테스트 케이스는 모두 서로 다르다.

각 테스트 케이스마다 조건을 만족하는 경로를 한 줄에 출력한다. 경로는 실행 순서대로 인접한 칸으로 이동하는 명령 문자로 이루어진다. D는 아래로, U는 위로, L은 왼쪽으로, R은 오른쪽으로 이동하는 명령이다. 조건을 만족하는 경로가 여러 개이면 그중 아무거나 출력한다. 조건을 만족하는 경로가 없으면 경로 대신 -1을 출력한다.

예제에는 테스트 케이스가 세 개 있다.

첫 번째 테스트 케이스에서 최단 경로의 길이는 6걸음이며, 최단 경로는 DRRRDD 하나뿐이다. 그 밖에 최단 경로가 아닌 단순 경로가 세 개 있다. DDRURRDD와 DRRURDDD는 길이가 8이고, DDRURURDDD는 길이가 10이다. 이 중 어느 것을 출력해도 된다.

두 번째 테스트 케이스에는 가능한 단순 경로가 여덟 개 있지만 모두 길이가 같아서 모두 최단 경로다.

세 번째 테스트 케이스에서는 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 빈 칸만 지나는 경로가 없다.