Map Reduce (Small)

비디오 게임 디자이너 벤은 곧 나올 증강 현실 모바일 게임의 지도를 만들고 있다. 최근 만든 지도는 $R$개의 행과 $C$개의 열로 이루어진 격자이다. 각 칸은 빈 칸을 뜻하는 ., 지나갈 수 없는 벽을 뜻하는 #, 하나뿐인 출발 위치 S, 하나뿐인 도착 위치 F 중 하나이다. 예를 들어 지도는 다음과 같을 수 있다.

#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############

경로는 벽을 지나지 않고 한 칸에서 다른 칸으로 가는 이동(위, 아래, 왼쪽, 오른쪽 한 칸)의 나열이다.

벤은 다음 조건을 모두 만족하는 지도를 좋은 지도라고 부른다.

• 임의의 두 빈 칸 사이에 경로가 있다. 출발 위치와 도착 위치도 빈 칸으로 친다.
• 구조가 튼튼하려면 벽끼리 꼭짓점만이 아니라 변으로 맞닿아야 한다. 지도의 모든 $2 \times 2$ 영역에 대해, 그 영역에 벽이 정확히 두 개 있으면 두 벽은 같은 행이나 같은 열에 있다. 즉 벽이 아래 두 가지 배치 중 하나로 놓인 $2 \times 2$ 영역은 없다.

#.   .#
.#   #.

• 경계는 모두 벽이다. 맨 위 행, 맨 아래 행, 맨 왼쪽 열, 맨 오른쪽 열에 있는 칸이 경계이다.

최단 경로의 길이는 출발 위치에서 도착 위치까지 가는 데 필요한 최소 이동 횟수이다. 위 예시에서 최단 경로의 길이는 17이다.

벤은 이 지도가 친구들에게 너무 어렵다는 것을 깨닫고, 벽 몇 개를 없애 난이도를 낮추려고 한다. 벽을 0개 이상 없애서, 결과 지도가 여전히 좋은 지도이면서 출발 위치에서 도착 위치까지 최단 경로의 길이가 정확히 $D$가 되게 할 수 있는지 알고 싶다. 길이가 $D$인 경로가 있는 것만으로는 부족하고, 최단 경로의 길이가 $D$여야 한다.

예를 들어 $D = 15$이면 도착 위치 바로 아래의 벽을 없애서 최단 경로의 길이가 15인 좋은 지도를 얻을 수 있다.

#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############

$D = 5$이면 방법이 없다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $R$, $C$, $D$가 공백으로 구분되어 주어진다. 각각 지도의 행 수, 열 수, 벽을 없앤 뒤 원하는 최단 경로의 길이이다. 다음 $R$개의 줄에는 벤의 지도가 한 줄에 $C$개의 문자(., #, S, F)로 주어진다.

주어지는 지도는 항상 좋은 지도이다.

제한

• $1 \le T \le 100$
• 각 테스트 케이스에는 S와 F가 정확히 하나씩 있다.
• 입력 파일의 크기는 3MB 이하이다.
• $3 \le R \le 40$
• $3 \le C \le 40$
• $1 \le D \le 1600$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 POSSIBLE 또는 IMPOSSIBLE이다. 벽 몇 개를 없애서 지도가 여전히 좋은 지도이면서 최단 경로의 길이가 정확히 $D$가 되게 할 수 있으면 POSSIBLE, 없으면 IMPOSSIBLE이다.

답이 POSSIBLE이면 이어서 아래 절차로 얻은 지도를 $C$개의 문자로 된 $R$개의 줄에 출력한다. 없앤 벽은 .로 바꿔 쓴다.

현재 지도에서 최단 경로의 길이를 $L$이라 하자. 칸의 순서는 위쪽 행이 먼저이고, 같은 행에서는 왼쪽 칸이 먼저이다. 경계에 있지 않고, 그 벽 하나만 없앴을 때 지도가 여전히 좋은 지도인 벽을 후보라고 부른다. $L \ne D$인 동안 다음을 반복한다.

1. 없앴을 때 $L$이 정확히 2 줄어드는 후보가 있으면, 그런 후보 중 칸의 순서로 가장 앞선 벽을 없앤다.
2. 그런 후보가 없으면, 없애도 $L$이 변하지 않는 후보 중 칸의 순서로 가장 앞선 벽을 없앤다.

처음 주어진 지도에서 $L = D$이면 벽을 하나도 없애지 않는다. 이 문제에서 답이 POSSIBLE인 모든 테스트 케이스에서 이 절차는 항상 $L = D$에 도달한다.

예제 1은 문제 설명의 예시이다. 도착 위치 바로 아래의 벽을 없애도 최단 경로의 길이가 15가 되지만, 도착 위치 바로 왼쪽의 벽이 칸의 순서로 더 앞서고 이 벽을 없애도 최단 경로가 2 줄어든다. 따라서 절차는 이 벽을 없앤다.

예제 2에서는 벽을 없애 최단 경로의 길이를 2나 4 등으로 만들 수 있지만, 정확히 3으로 만들 방법은 없다.

예제 3에서는 처음부터 최단 경로의 길이가 11이므로 벽을 없앨 필요가 없다.