题目描述

在很久以前的黄金时代，澳大利亚的土地是矩形的，它可以被划分成 $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$。

详细子任务分值及附加条件如下表。