很久很久以前，在梦幻时代，澳大利亚是一个由 $R$ 行 $C$ 列组成的平坦网格，每个网格单元最初都是陆地。行从北到南编号为 $1$ 到 $R$，列从西到东编号为 $1$ 到 $C$。位于第 $r$ 行第 $c$ 列的单元格记作 $(r, c)$。有一天，伟大的彩虹蛇从 $(s_r, s_c)$ 处破土而出，在澳大利亚大地上游走，所过之处皆化为河流。蛇进行了 $M$ 次连续的移动，每次移动到当前位置的正北 (N)、正南 (S)、正东 (E) 或正西 (W) 方向的相邻单元格，并将该单元格变为河流。蛇破土而出的初始单元格 $(s_r, s_c)$ 也变成了河流。

数百万年后的今天，你想要购买一个矩形区域的单元格，以纪念彩虹蛇创造河流的壮举。你需要为矩形区域内的每个陆地单元格选择一种颜色。你希望尽可能多地使用不同的颜色，但必须满足以下条件：矩形区域内每一对相邻的陆地单元格必须使用相同的颜色。如果两个单元格共享一条边，则称它们是相邻的。你不能为矩形区域外的任何陆地单元格选择颜色，也不能为矩形区域内的河流单元格选择颜色。

给定彩虹蛇的移动路径，你需要确定对于 $Q$ 个矩形区域中的每一个，你可以为其中的陆地单元格选择的最大不同颜色数量。

实现细节

你需要实现 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$ 次。

  • 此函数应返回一个整数：根据你的规则，在以 $(ar, ac)$ 为左上角、$(br, bc)$ 为右下角的矩形区域内，陆地单元格可以选择的最大不同颜色数量。
  • 你可以假设 $1 \le ar \le br \le R$ 且 $1 \le ac \le bc \le C$。

请查阅提供的模板文件，以获取有关针对特定编程语言实现解决方案的更多详细信息。

样例

样例输入 1

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

样例输出 1

0
2
1
3

子任务

对于所有子任务，$0 \le M \le 100\,000$ 且 $R, C, Q \ge 1$。

Figure 1. 样例输入中四个矩形区域的示意图