[APIO2017] 斑斓之地

本题原为交互题，这里采用传统题形式进行评测。

在很久以前的黄金时代，澳大利亚的土地是矩形的，它可以被划分成 $R$ 行 $C$ 列的网格状，行的编号从北到南依次为 $1$ 到 $R$ ，列的编号从西到东依次为 $1$ 到 $C$，$(r,c)$ 表示第 $r$ 行第 $c$ 列的土地。一天，伟大的彩虹蛇从 $(s_r,s_c)$ 出发在澳大利亚的土地上移动，彩虹蛇连续进行了 $M$ 次移动，每次它会向正北 (`N`)、正南 (`S`)、正东 (`E`) 或正西 (`W`) 方向移动一格，其经过的所有的格子（包括起点和终点）都会变成河流。保证在任一时刻，彩虹蛇都不会离开这片 $R$ 行 $C$ 列的矩形土地。 数百万年之后，你想购买一块矩形区域纪念伟大的彩虹蛇。你想给所购买矩形区域内每一块不是河流的格子都染上颜色，要求相邻的格子颜色必须相同，两个格子相邻当且仅当两个格子有一条公共边，你所购买区域之外的格子无须染色。 现在给出彩虹蛇 $M$ 次移动的方向，你有 $Q$ 个购买矩形区域的方案，问每个方案最多能够将土地染上多少种不同的颜色。

第一行：四个整数 $R$，$C$，$M$ 和 $Q$； 第二行：两个整数 $s_r$ 和 $s_c$； 第三行: 一个包含 $M$ 个字符的字符串 $S$，每个字符是 `N`、`S`、`E`、`W` 之一（如果 $M=0$ 则此行留空）； 第四到 $Q+3$ 行: 每行四个整数 $a_r,a_c,b_r$ 和 $b_c$，表示你购买的土地范围，左上角是 $(a_r,a_c)$，右下角是 $(b_r,b_c)$。

对于每个询问做出回答，输出最多能够将土地染上多少种不同的颜色。

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

### 样例解释 样例对应下图，其中蓝色代表河流。  ### 数据范围 对于所有测试数据，$0\le M\le 10^5$，并且 $R,C,Q\ge 1$，对于每个购买矩形土地的方案，都有 $1 \le a_r \le b_r \le R, 1 \le a_c \le b_c \le C$。 详细子任务分值及附加条件如下表。 |子任务编号|分值|$R$|$C$|$Q$| |:-:|:-:|:-:|:-:|:-:| |$1$|$11$|$R\le 50$|$C\le 50$|$Q\le 1000$| |$2$|$12$|$R=2$|$C\le 2\times 10^5$|$Q\le 10^5$| |$3$|$24$|$R\le 2\times 10^5$|$C\le 2\times 10^5$|$Q=1$| |$4$|$27$|$R\le 1000$|$C\le 1000$|$Q\le 10^5$| |$5$|$26$|$R\le 2\times 10^5$|$C\le 2\times 10^5$|$Q\le 10^5$|