Warez Test

Jimmy wants to marry Christine, the daughter of Mr. Warez, who owns almost every warehouse in town. Mr. Warez only lets his daughter marry someone who works for him, and no one may work for him without knowing how to push boxes in a warehouse properly. So Jimmy must first pass the famous "Warez Test."

Each map shows the layout of a warehouse as a grid of squares. Every square is a wall, holds a single box, or is empty. Some squares are marked as targets, and exactly one square is Jimmy's starting position.

Jimmy moves one square at a time in one of four directions: north (up), west (left), east (right), or south (down). He may step onto an empty square, or onto a square that holds a box if that box can be pushed one square further in the same direction, which requires the square just beyond the box to be empty. A wall square is never empty. Therefore a single move pushes at most one box, and that box moves exactly one square; Jimmy can never push a box into a wall or into another box.

The first and last rows and the first and last columns of every map are always walls. Every map has exactly as many boxes as target squares, and there is always at least one box. Jimmy's task is to move so that in the end every box stands on a target square. The length of a solution is the number of Jimmy's moves, whether or not a move pushes a box. Find a solution with the fewest moves; every map has at least one solution.

The first line contains the number of scenarios (maps).

For each map, the first line contains two integers: the number of rows and the number of columns (each at most 15), separated by a space. The next lines describe the map, one row per line, where 'X' is a wall, 'T' is a target square, and '.' is an empty square.

The following line contains Jimmy's starting position as two integers, the row and the column, separated by a space. The next line contains the number of boxes. Each of the following lines gives the starting position of one box as its row and column, separated by a space.

Rows and columns are numbered from 0, starting at the upper-left corner.

For each scenario, first print a line "Scenario #i:", where i is the scenario number starting from 1. On the next line, print the sequence of Jimmy's moves in a shortest solution, using 'n' for north (up), 'w' for west (left), 'e' for east (right), and 's' for south (down). If several solutions use the fewest moves, print the lexicographically smallest such sequence, comparing the strings character by character in the usual order where e < n < s < w (if no move is needed, print an empty line). Print a blank line between the outputs of two consecutive scenarios.