2310 [APIO2017] Land of the Rainbow Gold

A long long time ago, in the Dreamtime, Australia was a flat grid of $R$ rows and $C$ columns and each grid cell was land. The rows were numbered $1$ to $R$ from North to South, and the columns were numbered $1$ to $C$ from West to East. The cell in row $r$ and column $c$ was denoted as $(r,$ $c)$. One day, the great rainbow serpent rose from the earth at $(s_r,$ $s_c)$, and moved across Australia, creating rivers wherever it slid. The serpent made $M$ consecutive moves, each time moving to the cell directly North (N), South (S), East (E) or West (W), turning the cell into river. The cell $(s_r,$ $s_c)$ was also turned into river.

Now, millions of years later, you would like to purchase a rectangular block of cells to commemorate the creation of the rivers by the rainbow serpent. You will choose a different colour for each land cell inside your rectangular block. You would like to use as many different colours as possible but insist that every pair of adjacent land cells inside your block share the same colour. Two cells are adjacent if they share an edge. You will not choose a colour for any land cells outside your block, nor will you choose a colour for the river cells inside your block.

Given the moves made by the rainbow serpent, you would like to determine the maximum number of different colours you can choose for land cells in each of $Q$ rectangular blocks of cells.

Line 1: four integers $R,$ $C,$ $M$ and $Q$;
Line 2: two integers $s_r$ and $s_c$;
Line 3: a string $S$ consisting of $M$ characters, each N, S, E or W (this line should be left blank if $M = 0$);
Lines 4 to $Q$+3: four integers $a_r$, $a_c$, $b_r$ and $b_c$.

For every request, output the maximum number of different colours you can choose for land cells in the rectangular block.

For all subtasks, $0 ≤ M ≤ 10^5$ and $R, C, Q ≥ 1$.