Bacteria Trap Simulation

You are given a rectangular grid of N rows and M columns, with rows numbered 1 to N from top to bottom and columns numbered 1 to M from left to right. Each cell contains an integer and there are K bacteria placed in some of the cells. Additionally, a trap is placed in one specified cell. Each bacterium has an initial direction (one of N, E, S, W) and moves according to the following rules every second:

• At its current cell, the bacterium reads the integer \(X\) in that cell.
• The bacterium rotates clockwise by \(90^\circ\) exactly \(X\) times. (That is, if the current direction is represented as an angle \(\theta\), then the new direction becomes \(\theta + 90X\) modulo \(360\).)
• Now, if moving one cell in this new direction would leave the grid (i.e. the bacterium is facing the boundary), it instead rotates an additional \(180^\circ\) (i.e. it reverses its direction).
• Then the bacterium moves into the adjacent cell in the direction it is facing.

All bacteria move simultaneously. When, after a move, every bacterium is located in the trap cell at the same time, the trap is activated and all bacteria are eliminated within one second. Your task is to determine at what time (in seconds) all bacteria are eliminated. If the bacteria never all meet in the trap cell simultaneously, output -1.

Note: The final answer is the time at which the trap is activated plus one second (the one second needed to eliminate the bacteria).

inputFormat

The input is given as follows:

1. First line contains two integers \(N\) and \(M\) representing the number of rows and columns.
2. The next \(N\) lines each contain \(M\) integers. The \(j\)-th integer in the \(i\)-th line represents the number \(X\) in the cell at row \(i\), column \(j\).
3. The next line contains an integer \(K\), the number of bacteria.
4. Each of the following \(K\) lines contains two integers and a character: r c d. This indicates that a bacterium is initially at row \(r\), column \(c\) with initial direction d (which is one of N, E, S, or W).
5. The last line contains two integers tr tc, representing the row and column of the trap cell.

All row and column indices are 1-indexed.

outputFormat

Output a single integer: the time (in seconds) when all bacteria are eliminated. If they never all simultaneously enter the trap cell, output -1.

sample

2 2
1 1
1 1
1
1 1 N
2 2

3