탈출

제임스 B.는 가장 위험하고 화려한 임무를 맡는 비밀 요원이다. 이번 임무에서 그는 기밀 문서 묶음의 사본을 손에 넣어, 자신의 팀이 경쟁자들보다 앞서 나가도록 해야 한다.

최고의 요원답게 제임스는 문서가 네트워크에 연결되지 않은 컴퓨터에 보관된 건물에 손쉽게 침투해 USB에 자료를 복사했다. 그러나 건물을 빠져나오던 중, 한 교수가 시험용으로 설치해 둔 침입 탐지 장치를 건드렸고, 지금 그는 대학 경비대에 쫓기고 있다.

경비대의 차량은 제임스의 차를 따라잡을 수 없다. 그가 멈추지 않고 계속 달리는 한, 그들은 뒤쫓을 수 있을 뿐 결코 붙잡지 못한다. 몇 분 뒤 그를 태울 탈출 헬리콥터가 도착할 예정이다. 헬리콥터는 정해진 픽업 지점에서 제한된 시간 동안만 기다릴 수 있으므로, 제임스는 헬리콥터가 도착한 뒤 가능한 한 빨리, 즉 딱 맞추어 그곳에 도착하려 한다. 픽업 지점에서 기다리면 경비대에 따라잡히므로 그는 멈출 수 없고, 대신 달리는 차의 지붕에서 공중에 떠 있는 헬리콥터로 뛰어오른다.

도시의 지도, 제임스의 출발 위치(대학), 픽업 지점, 헬리콥터가 도착하는 시각, 그리고 헬리콥터가 최대 몇 초 동안 기다릴 수 있는지가 주어진다. 헬리콥터가 아직 기다리고 있는 동안 제임스가 픽업 지점에 도달할 수 있는 가장 이른 시각을 구하라.

제임스는 초당 한 칸의 속도로 이동하며, 목표 칸이 허용하는 한 북, 동, 남, 서 네 방향으로 움직일 수 있다(아래 표 참고). 경비대가 바짝 뒤쫓고 있어 유턴을 할 수 없고, 제자리에 멈출 수도 없으므로 항상 인접한 칸으로 이동해야 하지만 방금 지나온 칸으로는 되돌아갈 수 없다.

칸은 다음 문자로 표현된다.

제임스가 시각 $0$에 서 있는 대학은 U로 표시된다. 헬리콥터가 시각 $t$에 도착하는 픽업 지점은 X로 표시된다. 첫 이동에서는 인접한 칸이 허용하는 한 어느 방향으로든 갈 수 있다. 필요하다면 예정된 도착 시각 이전에 픽업 지점을 지나갈 수도 있다.

첫 줄에는 시나리오의 수가 주어진다.

각 시나리오는 두 정수 $R$과 $C$($1 \le R, C \le 50$)가 적힌 줄로 시작한다. 이어지는 $R$개의 줄에는 각각 도시의 배치를 나타내는 $C$개의 문자가 있다. 시나리오의 마지막 줄에는 헬리콥터가 도착하기까지의 시간 $t$(초)와 헬리콥터가 제임스를 기다릴 수 있는 시간 $d$(초)를 나타내는 두 정수가 주어진다($1 \le t, d \le 600$).

각 시나리오마다 먼저 “Scenario #i:”가 적힌 줄을 출력한다. 여기서 $i$는 1부터 시작하는 시나리오 번호이다. 다음 줄에는 $t \le t' < t + d$이면서 제임스가 정확히 $t'$초 후에 픽업 지점에 도달할 수 있는 가장 작은 $t'$를 출력하고, 헬리콥터로 탈출할 방법이 없으면 “Impossible”을 출력한다. 연속한 시나리오 사이는 빈 줄로 구분한다.