#2310. 「APIO2017」斑斓之地

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

在很久以前的黄金时代,澳大利亚的土地是矩形的,它可以被划分成 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 ,每个字符是 NSEW 之一(如果 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

样例说明

样例中染色方案如下图所示。

rainbow.png

数据范围与提示

对于所有测试数据, 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 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