Description

In the distant Golden Age, the land of Australia was rectangular and could be divided into a grid with $R$ rows and $C$ columns. Rows are numbered $1$ to $R$ from north to south, and columns are numbered $1$ to $C$ from west to east. The cell $(r, c)$ denotes the land in row $r$ and column $c$. One day, the great Rainbow Serpent started at $(s_r, s_c)$ and moved across Australia. The serpent made $M$ consecutive moves, each time moving one cell to the north (N), south (S), east (E), or west (W). Every cell it passed through (including the start and end cells) turned into river. It is guaranteed that the Rainbow Serpent never leaves the $R \times C$ rectangular land at any time.

Millions of years later, you want to buy a rectangular area to commemorate the great Rainbow Serpent. You want to color every non-river cell inside the purchased rectangle, with the requirement that adjacent cells must have the same color. Two cells are adjacent if and only if they share a common side. Cells outside your purchased area do not need to be colored.

You are given the $M$ movement directions of the Rainbow Serpent and $Q$ candidate rectangular regions to purchase. For each region, determine the maximum number of different colors you can use.

Input Format

The first line contains four integers $R$, $C$, $M$, and $Q$.

The second line contains two integers $s_r$ and $s_c$.

The third line contains a string $S$ of $M$ characters, each being one of N, S, E, or W (if $M=0$, this line is left blank).

Lines $4$ through $Q+3$: each line contains four integers $a_r$, $a_c$, $b_r$, and $b_c$, describing the land you intend to purchase, whose top-left corner is $(a_r, a_c)$ and bottom-right corner is $(b_r, b_c)$.

Output Format

For each query, output the maximum number of different colors that the land can be painted with.

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

0
2
1
3

Hint

Sample Explanation

The sample corresponds to the figure below, where blue cells represent rivers.

Constraints

For all testdata, $0 \le M \le 10^5$, and $R, C, Q \ge 1$. For every purchased rectangle, $1 \le a_r \le b_r \le R$ and $1 \le a_c \le b_c \le C$.

The detailed subtask scores and additional conditions are as follows.

Translated by ChatGPT 5