Path of Least Persistence

Bob Roberts runs a company that makes party games. One of them is a puzzle labyrinth. Every square of a rectangular grid holds a puzzle, and solving it tells the player which square to move to next. The player always starts at the upper left square and keeps solving puzzles until reaching the destination, the lower right square.

The solution of a square has the form rD, where r is the number of squares to move and D is the direction: N for up, S for down, E for right, W for left. The destination square holds no puzzle. If a move lands outside the grid, the path stops there and never reaches the destination. If the path steps on a square it has already used, it repeats the same loop forever and again never reaches the destination. The length of a path is the number of puzzles solved along it, which is the number of moves made.

Bob's layout program has a glitch, so its grids often have very long paths or paths that never reach the destination. Rebuilding a puzzle takes a lot of work, so Bob wants to change the solution of at most one square. A new solution also has the form rD, where r is a positive integer.

Write a square as (row, column) and count rows and columns from 0. For example, take the $3 \times 3$ grid whose solutions are 2E, 2S, 1S in the top row, 1S, 1N, 1W in the middle row, and 2N, 1E in the bottom row, with no solution on the destination square. The path runs (0, 0), (0, 2), (1, 2), (1, 1), (0, 1), (2, 1), (2, 2), so six puzzles are solved and the length is 6. Changing the solution at (0, 0) to 1E gives the path (0, 0), (0, 1), (2, 1), (2, 2) of length 3. Changing the solution at (0, 2) to 2S instead gives the path (0, 0), (0, 2), (2, 2) of length 2, and one change cannot do better.

Given a grid, find the one square whose solution should change so that the path from the start to the destination becomes as short as possible. Some grids need two or more changes before any path reaches the destination, and in some grids no change makes the current path shorter.

The input holds several test cases. The first line of a test case has the number of rows n and the number of columns m ($1 \le n \le 100$, $1 \le m \le 100$, $nm \ge 2$). After that come $nm - 1$ direction specifications, given row by row from the topmost row and left to right inside each row. A specification has the form rD, where r is a positive integer and D is one of N, S, E, W. The destination square, which is the last one, has no specification. A specification in the input may point outside the grid. The line breaks between specifications are not fixed.

A line holding two 0's ends the input. Do not process that line.

For each test case, print one line. The line starts with Case k: , where k is the test case number counted from 1, and continues with one of these three answers.

• If no single change reaches the destination, print impossible.
• If the current path reaches the destination and no single change makes it shorter, print none l, where l is the length of the current path.
• Otherwise print i j rD l, where i and j are the row and the column of the square to change, with row 0 at the top and column 0 at the left, rD is the new solution of that square, and l is the length of the new path.

If two or more changes give the shortest length, take the one with the lowest row number. If the row numbers tie, take the lowest column number, and if those tie as well, take the solution that comes first in the order 1E < 1N < 1S < 1W < 2E < 2N < ....