SCUSA Region ICPC Masthead ACM Balloon Logo
2014 ACM ICPC South Central USA Regional Programming Contest

1 - Map Puzzle

Map Puzzle

You must write a solver for a puzzle that depicts a map. Each tile is square with edges corresponding to markings on a map. There are six different possible edge types: Road (R), City (C), Farm (F), Stream (S), Lake (L), and Boulders (B). Tiles will fit in a grid of rows and columns where adjacent edges must match. Tile edges on the outer edge of the grid are not adjacent to any other tile edge, i.e. no wrap around.


The first line of input will contain the number of test cases, T (1 <= T <= 50).

The first line of each test case will contain the number of rows and columns R C in a grid, (1 <= R, C <= 50).

The next R * C lines will each contain a puzzle tile, represented as 4 characters indicating the North, East, South, and West sides.

The first tile read in for each puzzle is the starter tile. It is fixed, i.e. it cannot be rotated, and will be placed in the first row and first column of the grid. Subsequent tiles can be placed in any other location in the puzzle grid and can be rotated as necessary to find a proper fit.


Output consists of the completed puzzle, R * 5 lines each with C * 5 characters. Each 5x5 square represents a tile and looks like the following:

| F |
|L R|
| B |

Each puzzle is guaranteed to have a single solution.

Test cases will be separated by a single blank line.

Sample Input

2 3
2 2

Sample Output

| F || B || R |
|R R||R F||F S|
| C || L || F |
| C || L || F |
|L L||L B||B F|
| R || C || S |

| C || R |
|C C||C R|
| B || L |
| B || L |
|B S||S F|
| R || F |