P16729 [GKS 2019 #C] Wiggle Walk

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$ 是机器人最终所在的列。

样例 #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 完成