Map Reduce (Large)

Ben the brilliant video game designer is designing maps for his upcoming augmented-reality mobile game. Recently he created a map that is a matrix of R rows and C columns. The map consists of . characters for empty squares, # characters for impassable walls, a single start position S, and a single finish position F. For example, the map could look like this:

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

In Ben's game, a path is a sequence of steps (up, down, left, or right) that goes from one cell to another without passing through any wall.

Ben calls a map good if it has all of the following properties:

• There is a path between any two empty squares (including the start and finish positions).
• To keep the structure sound, walls must meet at edges and not only at corners. For every 2×2 region of the map, if the region contains exactly two walls, then those walls are in the same row or in the same column. In other words, no 2×2 region has its walls in either of these two configurations:

#.    .#
.#    #.

• The boundary consists only of walls. A cell is part of the boundary if it is in the top row, the bottom row, the leftmost column, or the rightmost column.

The length of the shortest path is the minimum number of steps needed to reach the finish position from the start position. In the example above, the shortest path takes 17 steps.

Being a clever mapmaker, Ben realized that this map is too hard for his friends. He wants to make it easier by removing some walls. Specifically, he wants to know whether he can remove zero or more walls so that the shortest path from start to finish takes exactly D steps and the resulting map is still good. Finding a path with D steps is not enough: D must be the length of the shortest path.

For example, if D = 15, removing the wall directly below the finish position gives a map that meets the requirements:

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

There is no solution if D = 5.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing three space-separated integers R, C, and D: the number of rows and columns of the map, and the desired number of steps in the shortest path from start to finish after removing walls. R lines follow, each with C characters (each one of ., #, S, or F) describing Ben's map.

The given map is guaranteed to be good, as defined in the statement.

Limits

• $1 \le T \le 100$
• Each test case contains exactly one S and exactly one F.
• The input file is at most 3MB in size.
• $3 \le R \le 1000$
• $3 \le C \le 1000$
• $1 \le D \le 10^6$

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1). y is POSSIBLE if walls can be removed so that the map is good and its shortest path is D, and IMPOSSIBLE otherwise.

If the answer is POSSIBLE, then output R more lines of C characters each: the map built by the procedure below. Print each removed wall as . instead of #.

Call a ., S, or F cell an empty cell. A wall cell w is removable if it satisfies all three of these conditions:

1. w is not on the boundary.
2. The map obtained by changing w to . is good.
3. It is not the case that the cells above and below w are empty while the cells to its left and right are walls. It is also not the case that the cells to the left and right of w are empty while the cells above and below it are walls.

The procedure starts from Ben's map. If the shortest path of the current map is exactly D, stop and output the current map. Otherwise, among the removable walls of the current map, pick the one in the topmost row, breaking ties by the leftmost column, change it to ., and check again. Whenever the answer is POSSIBLE, this procedure always stops at a map whose shortest path is D. If Ben's map already has shortest path D, output it unchanged.

Sample case #1 is the example from the statement. The map shown there (with the wall directly below the finish position removed) is also a good map with shortest path 15, but the procedure produces a different map that removes five walls, and that map is the required output.

In sample case #2, walls can be removed to make the shortest path 2 or 4, for example. However, there is no way to make the shortest path exactly 3.

In sample case #3, the shortest path already takes 11 steps, so no walls need to be removed.