P13059 [GCJ 2020 #1C] Overexcited Fan

今天将是你终于能和猫咪 Peppurr 合影的日子！ Peppurr 即将在你的城市巡游。这座城市有无限多条南北走向和东西走向的无限长街道。任意两条垂直街道的交点称为**十字路口**。从任意一个十字路口出发，往四个方向（北、东、南、西）最近的十字路口都恰好相隔一个街区。 你已知 Peppurr 巡游的完整路径。你的目标是**在 Peppurr 到达某个巡游路线的十字路口的同时**，你也到达该路口，并且希望尽可能快地完成这件事。这就是你与 Peppurr 合影的方式！ Peppurr 的巡游起点位于你当前位置以东 $\mathbf{X}$ 个街区、以北 $\mathbf{Y}$ 个街区的十字路口。你和 Peppurr 每走完一个完整街区都需要恰好一分钟，且每分钟结束时必须到达一个十字路口；你们都不能走部分街区。 Peppurr 沿着预定路径移动。每分钟，你可以选择**静止不动**，或者选择向四个方向之一（北、东、南、西）移动一个街区。你和 Peppurr 都只沿街道行走。 如果你和 Peppurr **同时到达同一个十字路口**，你就能成功合影（包括巡游的最后一个路口）。但 Peppurr 在巡游结束后不再接受合影，因此即使只晚一分钟到达巡游终点，也无法合影。 你有可能和 Peppurr 合影吗？如果可能，最快需要多少分钟？

输入的第一行包含测试用例数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例，每个用例占一行，包含两个整数 $\mathbf{X}$、$\mathbf{Y}$ 和一个字符串 $\mathbf{M}$。表示 Peppurr 的巡游起点位于你当前位置以东 $\mathbf{X}$ 个街区、以北 $\mathbf{Y}$ 个街区的十字路口。字符串 $\mathbf{M}$ 是 Peppurr 的移动序列，其中第 $i$ 个字符为 $\mathbf{N}$（北）、$\mathbf{E}$（东）、$\mathbf{S}$（南）或 $\mathbf{W}$（西），对应巡游第 $i$ 分钟 Peppurr 移动的方向。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始）。如果无法与 Peppurr 合影，$y$ 为 `IMPOSSIBLE`；否则 $y$ 为从巡游开始到成功合影所需的最少分钟数。

**样例解释** 在样例 #1 中，你可以向东走 4 个街区，在巡游的最后一个十字路口与 Peppurr 合影。 在样例 #2 中，巡游起点位于你以东 3 个街区。无论如何移动，你都无法与 Peppurr 合影。 在样例 #3 中，巡游路线距离你太远，无法在巡游结束前合影。 在样例 #4 中，Peppurr 会在 1 分钟后到达你的位置，因此你甚至不需要移动！注意只能在十字路口合影，如果你向北移动而 Peppurr 向南移动，虽然会在非路口处相遇，但无法在 0.5 分钟时合影。 在样例 #5 中，你可以先向北走 2 次，再向东走 2 次，然后静止不动，下一分钟即可合影。其他路径也可能在 5 分钟时合影，但无法更快。 以下两个样例不会出现在测试集 1 或 2 中，但可能出现在测试集 3： ``` 2 3 2 SSSW 4 0 NESW ``` 正确输出应为： ``` Case #1: 4 Case #2: 4 ``` 注意在样例 #1 中，你可以在起点以南 1 个街区、以东 2 个街区的十字路口与 Peppurr 合影。在样例 #2 中，Peppurr 沿小正方形移动，当其返回起点时即可合影。 **数据范围** - $1 \leqslant \mathbf{T} \leqslant 100$。 - $(\mathbf{X}, \mathbf{Y}) \neq (0, 0)$（巡游起点与你不在同一路口）。 **测试集 1（4 分，可见判定）** - $0 \leqslant \mathbf{X} \leqslant 10$。 - $0 \leqslant \mathbf{Y} \leqslant 10$。 - $1 \leqslant \mathbf{M} \text{ 的长度} \leqslant 8$。 - $\mathbf{M}$ 仅包含 $\mathbf{N}$ 或 $\mathbf{S}$。 **测试集 2（6 分，可见判定）** - $0 \leqslant \mathbf{X} \leqslant 1000$。 - $0 \leqslant \mathbf{Y} \leqslant 1000$。 - $1 \leqslant \mathbf{M} \text{ 的长度} \leqslant 1000$。 - $\mathbf{M}$ 仅包含 $\mathbf{N}$ 或 $\mathbf{S}$。 **测试集 3（12 分，可见判定）** - $0 \leqslant \mathbf{X} \leqslant 1000$。 - $0 \leqslant \mathbf{Y} \leqslant 1000$。 - $1 \leqslant \mathbf{M} \text{ 的长度} \leqslant 1000$。 - $\mathbf{M}$ 可包含 $\mathbf{N}$、$\mathbf{E}$、$\mathbf{S}$ 或 $\mathbf{W}$。 翻译由 DeepSeek V3 完成