题目描述

Banny 刚刚买了一个新的可编程机器人。为了测试自己的编程技能，他将机器人放置在一个有 $R$ 行（从北到南编号为 $1$ 到 $R$）和 $C$ 列（从西到东编号为 $1$ 到 $C$）的方格网格中。位于第 $r$ 行、第 $c$ 列的方格记为 $(r, c)$。

机器人初始位于方格 $(S_R, S_C)$。Banny 会给机器人下达 $N$ 条指令。每条指令是 $\mathsf{N}$、$\mathsf{S}$、$\mathsf{E}$ 或 $\mathsf{W}$ 之一，分别指示机器人向北、向南、向东或向西移动一个方格。

如果机器人移动到一个它曾经到过的方格，机器人将继续沿相同方向移动，直到到达一个它从未到过的方格为止。Banny 给出的指令绝不会导致机器人移出网格。

你能帮助 Banny 确定机器人在执行完 $N$ 条指令后最终停留在哪个方格吗？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含五个整数 $N$、$R$、$C$、$S_R$ 和 $S_C$，分别表示指令的条数、行数、列数、机器人的起始行和起始列。

随后一行包含一个长度为 $N$ 的字符串；其中第 $i$ 个字符是 Banny 给机器人的第 $i$ 条指令（如上所述，为 $\mathsf{N}$、$\mathsf{S}$、$\mathsf{E}$ 或 $\mathsf{W}$ 之一）。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: r c，其中 $x$ 是测试用例编号（从 $1$ 开始），$r$ 是机器人最终所在的行，$c$ 是机器人最终所在的列。

3
5 3 6 2 3
EEWNS
4 3 3 1 1
SESE
11 5 8 3 4
NEESSWWNESE

Case #1: 3 2
Case #2: 3 3
Case #3: 3 7

提示

样例 #1 对应左上角图示，样例 #2 对应右上角图示，样例 #3 对应下方的图示。每张图示中，黄色方格是机器人的起始方格，绿色方格是机器人的结束方格。

:::align{center} :::

限制条件

内存限制：$1$ GB。

$1 \le T \le 100$。

$1 \le R \le 5 \times 10^4$。

$1 \le C \le 5 \times 10^4$。

$1 \le S_R \le R$。

$1 \le S_C \le C$。

指令不会导致机器人移出网格。

测试集 1（可见）

$1 \le N \le 100$。

测试集 2（隐藏）

$1 \le N \le 5 \times 10^4$。

翻译由 DeepSeek V4 Pro 完成