탈출 경로

제국군 전함들에게 포위된 당신은 탈출하기 위해 어느 행성에 착륙해야 한다. 가장 좋은 방법은 현재 위치에서 가장 가까운 행성에 도달하는 것이다. 그러나 항법 장치가 손상되었으므로, 우주선에서 가장 가까운 행성을 찾는 프로그램을 직접 작성해야 한다.

우주 공간은 다음 네 종류의 문자로 이루어진 $m \times m$ 격자로 표현된다.

• s: 내 우주선
• w: 제국군 전함
• p: 행성
• -: 빈 공간

각 물체(우주선, 전함, 행성)의 위치는 격자에서의 위치이며, (행, 열)로 표기한다. 행과 열의 번호는 모두 $0$부터 시작하고, 맨 왼쪽 위 칸이 $(0, 0)$이다. 아래 표는 $4 \times 4$ 격자에서 각 칸의 좌표를 보여 준다.

두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 거리는 다음과 같다.

$$dist = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$

첫째 줄에 데이터 집합의 개수를 나타내는 양의 정수 $n$이 주어진다. 각 데이터 집합은 양의 정수 $m$이 적힌 줄로 시작하고, 이어서 정확히 $m$개의 문자로 이루어진 줄이 $m$개 주어진다. 각 문자는 s, w, p, - 중 하나이다. 각 데이터 집합에는 정확히 하나의 우주선 s와 하나 이상의 행성 p가 있다.

각 데이터 집합마다 한 줄을 출력한다. 현재 위치의 좌표, 콜론(:), 가장 가까운 행성의 좌표, 다시 콜론(:), 그리고 그 행성까지의 거리를 소수점 아래 둘째 자리까지 반올림한 값을 차례로 출력한다. 좌표는 공백 없이 (행,열) 형식으로 쓴다.

가장 가까운 행성이 여러 개라면, 격자를 위에서 아래로, 같은 행에서는 왼쪽에서 오른쪽으로 훑을 때 가장 먼저 나오는 행성(행 번호가 가장 작고, 그중에서 열 번호가 가장 작은 행성)을 출력한다.