헤이 구글, 드라이브!

Google Assistant와 Android Auto 팀은 음성 명령으로 운전할 수 있는 새 시제품 자동차를 함께 개발하고 있다. 초기 시제품은 자동차 시뮬레이터에 연결된 휴대폰을 통해 작동한다. 그런데 초기 테스터 한 명이 휴대폰을 변기에 빠뜨려 마이크가 고장 났고, 새 기능을 쓰기가 더 어려워졌다. 기회를 놓치고 싶지 않은 테스터는 그래도 이 기능을 쓸 수 있도록 도움을 요청한다.

초기 시제품은 $\mathbf{R}$행 $\mathbf{C}$열의 단순한 격자 위를 움직이며, 북, 남, 동, 서 네 가지 매우 단순한 음성 명령만 이해한다. 각 명령은 자동차가 해당 방향으로 정확히 한 칸 이동하려고 하게 만든다. 하지만 마이크 문제 때문에 시스템은 북과 남, 그리고 동과 서를 각각 잘못 알아들을 수 있다. 즉 북 명령은 자동차를 북 또는 남으로 움직이게 할 수 있고, 남 명령은 남 또는 북으로, 동 명령과 서 명령도 마찬가지로 동 또는 서로 움직이게 할 수 있다. 어떤 경우든 두 이동 방향은 같은 확률($1/2$)로 일어난다.

테스터는 각 칸이 벽, 위험 지점, 빈 칸 중 하나인 주행 격자를 설정했다. 명령으로 자동차가 벽이나 격자 바깥으로 이동하려 하면 자동차는 아무것도 하지 않는다. 명령으로 자동차가 위험 지점에 들어가면 자동차는 더 이상 명령을 수행할 수 없다.

테스터는 격자의 빈 칸 일부를 관심 있는 출발점으로, 나머지 일부를 관심 있는 도착점으로 표시했다. 관심 있는 출발점과 관심 있는 도착점의 쌍은, 출발점에서 음성 명령으로 자동차를 몰아 확률 $1 - 10^{-{10^{100}}}$ 이상으로 도착점에서 끝나게 하는 전략이 존재하면 주행 가능하다. 전략은 이전 명령의 결과에 따라 어떤 명령을 내릴지, 언제 멈출지를 고를 수 있다. 자동차가 위험 지점에 들어가면 움직이지 않으므로 도착점에 닿을 수 없다는 점에 유의하라. 테스터는 주행 가능한 모든 쌍의 목록을 찾아 주기를 원한다.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 나온다. 각 테스트 케이스는 격자의 행 수와 열 수인 두 정수 $\mathbf{R}$과 $\mathbf{C}$가 적힌 줄로 시작한다. 그다음 $\mathbf{C}$글자로 이루어진 문자열이 $\mathbf{R}$줄 주어진다. 이 중 $i$번째 줄의 $j$번째 글자 $\mathbf{G}_{i,j}$는 $i$행 $j$열의 칸을 다음과 같이 나타낸다.

• 마침표(.)는 관심 없는 빈 칸을 뜻한다.
• 샵(#)은 벽이 있는 칸을 뜻한다.
• 별표(*)는 위험 지점이 있는 칸을 뜻한다.
• 영문 소문자(a부터 z까지)는 관심 있는 출발점인 빈 칸을 뜻한다.
• 영문 대문자(A부터 Z까지)는 관심 있는 도착점인 빈 칸을 뜻한다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 주행 가능한 쌍이 없으면 NONE이다. 그렇지 않으면 $y$는 주행 가능한 모든 쌍을 출발점 글자, 도착점 글자 순으로 두 글자 문자열로 나타내고, 공백으로 구분하여 알파벳 순서대로 나열한 것이어야 한다.

• $1 \le \mathbf{T} \le 100$.
• 모든 $i, j$에 대해 $\mathbf{G}_{i,j}$는 마침표(.), 샵(#), 별표(*), 영문 소문자 또는 영문 대문자 중 하나이다.
• 집합 $\{\mathbf{G}_{i,j}\}$에는 영문 소문자가 1개 이상, 영문 대문자가 1개 이상 포함된다.
• 각 영문 소문자와 영문 대문자는 모든 $\mathbf{G}_{i,j}$ 중에서 최대 한 번만 나타난다.

예시 케이스 #1에서는 도착점에 닿을 때까지 west 명령을 반복하는 것만으로도 유효한 전략이 된다. 매번 도착점에 갈 확률은 $1/2$이고, 같은 자리에 머물 확률도 $1/2$이다. 따라서 $10^{101}$번 이하의 단계 안에 도착점에 가지 못할 확률은 $2^{-10^{101}} \lt 10^{-10^{100}}$이다.

예시 케이스 #2에서는 예시 케이스 #1과 비슷한 전략으로, 맨 윗줄(1)의 어떤 위치에서든 다른 어떤 위치로든 원하는 만큼 높은 확률로 자동차를 옮길 수 있다. 위에서 셋째 줄(2)의 벽이 아닌 모든 위치에 대해서도 마찬가지다. south 명령을 사용하면 같은 방식으로 왼쪽에서 셋째 열(3)의 벽이 아닌 위치들 사이를 오갈 수 있다. a와 c 모두 (1)을 써서 왼쪽에서 셋째 열로 간 뒤, (3)으로 Y 바로 옆까지 가고, (2)로 Y에 도달할 수 있으므로 aY와 cY는 모두 주행 가능하다. 다만 셋째 줄에서 north나 south 명령을 안전하게 쓰려면 셋째 열에서만 가능하다. 그렇지 않으면 자동차가 위험 지점에 들어갈 수 있다. 따라서 셋째 줄에서 넷째 줄로 안전하게 옮겨 갈 방법이 없고, aX와 cX는 주행 가능하지 않다. 반면 b에서는 비슷한 전략으로 X에 도달할 수 있고, X에서는 north나 south 명령을 반복해서 Y에 갈 수 있다(Y에 도달하면 멈추므로 위의 위험 지점에 들어갈 위험이 없다). 마지막으로 도착점 Z는 완전히 고립되어 있으므로 주행 가능한 쌍에 포함될 수 없다.

예시 케이스 #3에서는 관심 있는 출발점에서 관심 있는 도착점으로 가는 모든 경로가 위험 지점을 지나므로, 이 쌍은 주행 가능하지 않다.

예시 케이스 #4에서는 관심 있는 출발점 d만이 도착점 F에 도달하는 유효한 전략을 가진다.