Coloring the Land in the Age of the Rainbow Snake

In the golden age long ago, the land of Australia was a rectangle divided into a grid of \(R\) rows and \(C\) columns. The rows are numbered from north to south from \(1\) to \(R\) and the columns from west to east from \(1\) to \(C\). A cell at \((r, c)\) is the cell in row \(r\) and column \(c\).

One day, the great Rainbow Snake started its journey from \((s_r, s_c)\) and made \(M\) moves. In each move, it went one cell in one of the four directions: north (N), south (S), east (E) or west (W). Every cell it passed—including both the starting cell and the ending cell of each move—turned into a river. It is guaranteed that the snake never leaves the \(R \times C\) grid.

Millions of years later, you want to purchase a rectangular region to commemorate the great Rainbow Snake. In your chosen region, you plan to color every cell that is not a river. However, cells which share a common side and are both not river must be colored with the same color. (Two cells are adjacent if they share a common side.) You do not need to color cells outside the purchased rectangle.

Given the \(M\) moves of the Rainbow Snake and \(Q\) queries, where each query specifies a rectangular region you consider to buy, your task is to determine, for each query, the maximum number of different colors that can be applied. Essentially, this is the number of connected components (with respect to 4-directional connectivity) of non‐river cells within the region.

The moves follow the letter convention: N for north, S for south, E for east, and W for west.

inputFormat

The input is given as follows:

R C
s_r s_c
M
D
Q
r1 c1 r2 c2
r1 c1 r2 c2
... (Q queries in total)

Where:

• \(R, C\) are the dimensions of the grid.
• \((s_r, s_c)\) is the starting cell of the Rainbow Snake.
• \(M\) is the number of moves.
• D is a string of length \(M\) representing the moves (each character is one of N, S, E, W).
• \(Q\) is the number of queries.
• Each query consists of four integers \(r1\), \(c1\), \(r2\), \(c2\) representing the top-left and bottom-right cells of the rectangular region (with \(1 \le r1 \le r2 \le R\) and \(1 \le c1 \le c2 \le C\)).

outputFormat

For each query, output a single integer on a new line: the maximum number of different colors that can be applied, i.e. the number of connected components of non‐river cells in the specified rectangle.

sample

5 5
3 3
4
NESW
2
1 1 5 5
2 2 4 4

1
1