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.

Implementation Details

You need to implement the functions init and colours:

• init(R, C, sr, sc, M, S) — The grader will call this function first and exactly once.

  • $R$ and $C$: the number of rows and columns in the grid.
  • $s_r$ and $s_c$: the row and column where the serpent rose from the earth.
  • $M$: the number of moves the serpent made.
  • $S$: a string of length $M$: $S[i]$ is either N, S, E or W, denoting that the serpent's $i^{\text{th}}$ move was to the cell immediately North, South, East or West of its current location, for all $0\le i\le M-1$. You may assume that the serpent never left the grid.

• colour(ar, ac, br, bc) — After calling init once, the grader will call this function $Q$ times in a row.

  • This function should return a single integer: the maximum number of different colours you can choose for land cells in the rectangular block of cells with North-West corner $(a_r,a_c)$ and South-East corner $(b_r,b_c)$, according to your rules.
  • You may assume that $1\le a_r\le b_r\le R$ and $1\le a_c\le b_c\le C$.

Input Specification

The sample grader reads the input in the following format:

• 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$.

Sample Input

6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3

Sample Output

0
2
1
3

Explanation for Sample Output

Function calls	Return value	Explanation
init(6, 4, 3, 3, 9, "NWESSWEWS")		The module provides your program with the dimensions of the grid, the starting position of the serpent and the moves it made. There is no return value.
colour(2, 3, 2, 3)	$0$	The only cell in this rectangle is $(2,3)$, which is a river cell. Hence, you cannot choose a colour for any land cells.
colour(3,2,4,4)	$2$	The river separates the land cells into two regions: the first region containing the cell $(3,2)$, and the second region containing the cells $(3,4)$ and $(4,4)$. Therefore the maximum number of different colours you can choose is $2$.
colour(5, 3, 6, 4)	$1$	All the cells in this rectangle are land cells. Since all the land cells are connected, the maximum number of different colours you can choose is $1$.
colour(1, 2, 5, 3)	$3$	The river separates the land cells into three regions: the first region containing the cells $(1,2)$ and $(1,3)$, the second region containing the cell $(3,2)$ and the third region containing the cell $(5,3)$. Therefore the maximum number of different colours you can choose is $3$.

The blue, patterned cells are river cells.

Subtasks

For all subtasks, $0\le M\le 100000$ and $R,C,Q\ge 1$.

Subtask	Points	$R$	$C$	$Q$
$1$	$11$	$R\le 50$	$C\le 50$	$Q\le 1000$
$2$	$12$	$R=2$	$C\le 200000$	$Q\le 100000$
$3$	$24$	$R\le 200000$	$C\le 200000$	$Q=1$
$4$	$27$	$R\le 1000$	$C\le 1000$	$Q\le 100000$
$5$	$26$	$R\le 200000$	$C\le 200000$	$Q\le 100000$