Description

曼哈顿有许多很棒的街头小吃摊，但毫无疑问，味道最棒的是 Code Jam 可丽饼车！

你想找到这辆小吃车，但你只知道它在某个街道交叉口。你认为来自曼哈顿各地的人们正朝着这个交叉口走去，因此你会尝试找出最多人正前往的那个交叉口。

在本题中，曼哈顿是一张规则的网格，坐标轴与罗盘方向对齐，每个坐标轴的取值范围为 $0$ 到 $\mathbf{Q}$（包含 $0$ 和 $\mathbf{Q}$）。东西向的街道对应于 $y = 0, y = 1, y = 2, \cdots, y = \mathbf{Q}$ 的网格线，南北向的街道对应于 $x = 0, x = 1, x = 2, \cdots, x = \mathbf{Q}$ 的网格线，人们只能沿着这些街道行走。网格线的交点（如 $(0, 0)$ 和 $(1, 2)$）即为街道交叉口。两个交叉口之间的最短距离是曼哈顿距离，即横向距离与纵向距离的绝对值之和。

你知道有 $\mathbf{P}$ 个人的位置，他们都站在交叉口上，并且你知道每个人当前前进的方向：北（$y$ 增大方向）、南（$y$ 减小方向）、东（$x$ 增大方向）或西（$x$ 减小方向）。如果某个人当前的移动方向在曼哈顿网格中是通往某个交叉口的最短路径之一，则认为此人正朝该交叉口前进。例如，如果某人位于 $(x_0, y_0)$ 并向北移动，则他们正朝所有 $y > y_0$ 的交叉口前进。

你认为可丽饼车就在最多人正前往的交叉口处。此外，你认为岛屿的更南部和更西部更有可能有可丽饼车，因此如果有多个这样的交叉口，你会选择 $x$ 坐标最小的那个，如果仍有多个，则选择 $y$ 坐标最小的那个。你会选择哪个交叉口？

Input Format

输入的第一行包含测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 组测试用例。每组测试用例的第一行包含两个整数 $\mathbf{P}$ 和 $\mathbf{Q}$，分别表示人数和曼哈顿坐标的最大值。接下来的 $\mathbf{P}$ 行，每行包含两个整数 $\mathbf{X}_i$ 和 $\mathbf{Y}_i$，表示第 $i$ 个人当前所在的交叉口，以及一个字符 $\mathbf{D}_i$，表示该人前进的方向。$\mathbf{D}_i$ 是大写字母 N、S、E 或 W，分别代表北、南、东和西。

Output Format

对于每个测试用例，输出一行，格式为 Case #t: x y，其中 $t$ 是测试用例编号（从 1 开始），$x$ 和 $y$ 分别为你认为可丽饼车所在交叉口的横纵坐标。

3
1 10
5 5 N
4 10
2 4 N
2 6 S
1 5 E
3 5 W
8 10
0 2 S
0 3 N
0 3 N
0 4 N
0 5 S
0 5 S
0 8 S
1 5 W

Case #1: 0 6
Case #2: 2 5
Case #3: 0 4

Hint

样例解释

在样例 1 中，只有一个人，他从 $(5, 5)$ 向北移动。这意味着所有 $y \geqslant 6$ 的交叉口都是可丽饼车可能的位置。在这些位置中，选择 $x \geqslant 0$ 最小的，再选择 $y \geqslant 6$ 最小的。

在样例 2 中，有四个人都朝着 $(2, 5)$ 这个位置移动，没有其他位置有这么多人朝向。

在样例 3 中，八个人中有六个人都朝着 $(0, 4)$ 这个位置移动，没有其他位置有这么多人朝向。

数据范围

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $1 \leqslant \mathbf{P} \leqslant 500$。
• $0 \leqslant \mathbf{X}_i \leqslant \mathbf{Q}$，对所有 $i$。
• $0 \leqslant \mathbf{Y}_i \leqslant \mathbf{Q}$，对所有 $i$。
• 对所有 $i$，如果 $\mathbf{X}_i = 0$，则 $\mathbf{D}_i \neq \text{W}$。
• 对所有 $i$，如果 $\mathbf{Y}_i = 0$，则 $\mathbf{D}_i \neq \text{S}$。
• 对所有 $i$，如果 $\mathbf{X}_i = \mathbf{Q}$，则 $\mathbf{D}_i \neq \text{E}$。
• 对所有 $i$，如果 $\mathbf{Y}_i = \mathbf{Q}$，则 $\mathbf{D}_i \neq \text{N}$。

测试点 1（9 分，可见）

• $\mathbf{Q} = 10$。

测试点 2（18 分，隐藏）

• $\mathbf{Q} = 10^5$。

由 ChatGPT 4.1 翻译