题目描述

你们国家的航天局刚刚在一颗新行星上着陆了一辆火星车。行星表面可以看作是一个包含 $10^9$ 列（从西到东编号为 $1$ 开始）和 $10^9$ 行（从北到南编号为 $1$ 开始）的方格网格。记 $(w, h)$ 表示第 $w$ 列、第 $h$ 行的方格。火星车从方格 $(1, 1)$ 出发。

火星车可以通过发送程序来操控，程序包含一个字符串，字符串中的字符代表四个基本方向的移动。机器人按顺序执行字符串中的每个字符。火星车的移动规则如下：

• N：向北移动一个单位。
• S：向南移动一个单位。
• E：向东移动一个单位。
• W：向西移动一个单位。

此外，还有一种特殊指令 $\text{X}(\text{Y})$，其中 $\text{X}$ 是 $2$ 到 $9$（包含两端）之间的数字，$\text{Y}$ 是一个非空子程序。该指令表示机器人应重复执行子程序 $\text{Y}$ 共 $\text{X}$ 次。例如：

• 2(NWE) 等价于 NWENWE。
• 3(S2(E)) 等价于 SEESEESEE。
• EEEE4(N)2(SS) 等价于 EEEEENNNNSSSS。

由于行星是一个球体，第一列和最后一列相邻，因此从第 $10^9$ 列向东移动会使火星车移动到第 $1$ 列，从第 $10^9$ 行向南移动会使火星车移动到第 $1$ 行。类似地，从第 $1$ 列向西移动会使火星车移动到第 $10^9$ 列，从第 $1$ 行向北移动会使火星车移动到第 $10^9$ 行。给定一个机器人将要执行的程序，请确定机器人完成所有移动后的最终位置。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行，每行包含一个字符串：发送给火星车的程序。

输出格式

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

4
SSSEEE
N
N3(S)N2(E)N
2(3(NW)2(W2(EE)W))

Case #1: 4 4
Case #2: 1 1000000000
Case #3: 3 1
Case #4: 3 999999995

提示

在样例 #1 中，火星车向南移动三格，然后向东移动三格。

在样例 #2 中，火星车向北移动一格。由于行星是一个环面，这会将其移动到第 $10^9$ 行。

在样例 #3 中，发给火星车的程序等价于 NSSSNEEN。

在样例 #4 中，发给火星车的程序等价于 NWNWNWWEEEEWWEEEEWNWNWNWWEEEEWWEEEEW。

限制条件

$1 \le T \le 100$。

字符串表示一个有效的程序。

每个程序的长度在 $1$ 到 $2000$ 个字符之间（包含两端）。

测试集 1

单个测试用例中机器人执行的总移动步数不超过 $10^4$。

测试集 2

无额外限制。

翻译由 DeepSeek V4 Pro 完成