Submarine’s Secret Navigation

A submarine is secretly navigating through an ocean represented as an \(R \times C\) grid. In the grid, a cell marked with # is an island, and a cell marked with . is water. The submarine can only travel through water cells.

Every minute the submarine sends out a radio signal indicating the direction in which it plans to move. The signal is represented by one of the letters \(N\) (north), \(E\) (east), \(S\) (south), or \(W\) (west). However, some signals are not decipherable and are given as ?.

You are given an intercepted signal string of length \(M\) (for the last \(M\) minutes) and a map of the ocean. The submarine’s starting position is unknown (but it is known to be located on a water cell). Determine the number of distinct cells the submarine could be in after following the signals. Note that when a direction is unknown (?), the submarine might have chosen any of the four cardinal directions provided the destination cell is water. If a move would take the submarine to an island or off the grid, that particular branch of possibility is discarded.

Formally, let the grid be indexed with rows \(0\) to \(R-1\) and columns \(0\) to \(C-1\). For each water cell as a starting point, simulate the movement for each signal:

\[ (r, c) \to (r + dr, c + dc), \] where \( (dr, dc) \) is \((-1, 0)\) for \(N\), \((0, 1)\) for \(E\), \((1, 0)\) for \(S\), and \((0, -1)\) for \(W\). For a ? signal, any of the four directions may be chosen. Output the total number of distinct positions (cells) that the submarine could occupy after processing all \(M\) signals.

inputFormat

The input begins with two integers (R) and (C) representing the number of rows and columns of the ocean grid. Then follow (R) lines, each containing a string of length (C). Each character is either # (island) or . (water). Next is an integer (M) followed by a string of length (M) representing the intercepted signals. Each signal is one of N, E, S, W, or ? (unknown).

outputFormat

Output a single integer representing the number of distinct possible final positions of the submarine.

sample

3 3
...
.#.
...
2
NE

1