보물

오래된 여관에서 몬테수마의 전설적인 보물로 인도하는 지도를 손에 넣었다. 아즈텍인들은 잉카의 땅인 안데스 고원에 보물을 숨겨 두었다. 이 고원은 직사각형 모양이며, 위험한 균열(낭떠러지)이 곳곳에 나 있다. 지도에는 탐색을 시작해야 하는 위치와 보물의 위치가 표시되어 있다.

지도는 $w \times k$ 개의 문자로 이루어진 격자로 주어진다. 한 칸에서는 왼쪽, 오른쪽, 위, 아래로 인접한 칸으로만 이동할 수 있다. 균열을 피해 보물까지 가는 길을 찾되, 그 길은 반드시 최단 경로여야 한다. 또한 몬테수마의 저주를 피하려면, 이동 경로를 각각 왼쪽·오른쪽·위·아래로의 이동을 뜻하는 문자 L, P, G, D 로 이루어진 문자열로 적었을 때 사전순으로 가장 앞서는 최단 경로를 따라 보물에 도달해야 한다.

이 길을 손으로 일일이 찾는 것은 너무 번거롭기 때문에, 이를 대신 계산해 주는 프로그램을 작성하려고 한다.

입력의 첫 줄에는 연이어 주어지는 데이터 집합의 개수를 나타내는 작은 정수 하나가 주어진다. 각 데이터 집합의 형식은 다음과 같다.

첫 줄에는 두 정수 $w$ 와 $k$ 가 주어진다 ($1 \le w, k \le 1000$). 각각 지도의 행 수와 열 수를 의미한다. 이어지는 $w$ 개의 줄에는 각각 $k$ 개의 문자가 주어지며, 이것이 지도의 내용이다. 각 문자의 의미는 다음과 같다.

• . — 평범한 고원 지역
• X — 균열이 있는 지역
• S — 출발 위치
• * — 보물의 위치

각 데이터 집합마다, 출발 위치에서 보물까지 가는 최단 경로를 나타내는 문자열을 한 줄에 출력한다. 그러한 최단 경로가 여러 개라면 사전순으로 가장 앞서는 것을 출력한다. 출발 위치에서 보물에 도달할 수 없다면 BRAK 을 출력한다.