Amazing Maze

A maze consists of M rows and N columns of cells. Each cell has doors toward its four adjacent cells, but exactly one outgoing door is open at any moment. The door from A to B and the door from B to A work independently.

The initially open direction of every cell is given in the input. Once every minute, every open direction rotates 90 degrees clockwise in the order N, E, S, W, then back to N.

In one minute you may move one cell in the currently open direction from your current cell, or you may stay in place and wait for the door direction you want. If the currently open door points outside the maze, you cannot move during that minute but may still wait.

You start at cell (1, 1). Your goal is to collect all K treasure chests and reach cell (M, N). You may visit (M, N) before collecting every treasure, but the maze is escaped only when you are at (M, N) after collecting them all.

Find the minimum time required to escape the maze.

The input contains multiple test cases. Each test case begins with two integers M and N (2 <= M, N <= 100).

The next M lines each contain N characters. Each character is one of N, E, S, and W, indicating the initially open outgoing direction of that cell. For a cell at position (r, c), the directions N, E, S, and W point to (r - 1, c), (r, c + 1), (r + 1, c), and (r, c - 1), respectively.

Next, an integer K (1 <= K <= 8) is given. The following K lines each contain two integers R and C, the position of one treasure chest. No cell contains more than one treasure chest, and no treasure chest is placed at (1, 1) or (M, N).

The line 0 0 marks the end of the input.

For each test case, output the minimum time required to escape the maze.