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

实现细节

你需要包含头文件 rainbow.h。

你需要实现函数 init 和 colours:

• init(R, C, sr, sc, M, S) --- 该函数会在开始时调用并且只会调用一次

  • R 和 C: 表示网格的行数和列数
  • sr 和 sc: 彩虹蛇的起点坐标
  • M: 彩虹蛇移动的步数
  • S: 一个长度为 M 的字符串, S[i] 是N、S、E、W之一, 分别表示彩虹蛇的第 $i$ 次移动是向正北、正南、正东、正西移动一格，$0\le i\le M-1$ 。保证彩虹蛇不会移动到网格外面。

• colours(ar, ac, br, bc) --- 在调用init一次之后, 该函数会被总共调用 $Q$ 次

  • $(a_r,a_c)$ 表示你所购买矩形的西北角的格子的坐标，$(b_r,b_c)$ 表示你所购买矩形的东南角的格子的坐标，返回一个整数表示在这种购买方案下最多能够将土地染上多少种不同的颜色
  • $1\le a_r\le b_r\le R$, $1\le a_c\le b_c\le C$

请参考提供的模板文件以获取更多的细节。

样例测试程序

样例测试程序按照以下格式输入:

• 第1行:四个整数 $R$, $C$, $M$ 和 $Q$;
• 第2行:两个整数 $s_r$ 和 $s_c$;
• 第3行:一个包含 $M$ 个字符的字符串 $S$, 每个字符是N、S、E、W之一 (如果 $M=0$ 则此行应留空);
• 第4行到 $Q+3$ 行:每行四个整数$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 100000$, $R,C,Q\ge 1$。

在本题的 hack 中，你可以提交与样例交互库相同格式的输入，该输入需要满足 $1\le R,C\le 200000,1\le Q\le 100000,0\le M\le 100000$。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例及测评库下载