曼哈顿的街头食品摊贩有很多，但毫无疑问，最美味的当属 Code Jam 可丽饼摊！

你想找到这个摊位，但除了知道它位于某个街道路口外，对其位置一无所知。你认为曼哈顿各处的人们目前正朝着那个路口走去，因此你试图找出前往人数最多的那个路口。

就本题而言，曼哈顿是一个规则网格，其坐标轴与指南针方向对齐，每个轴的范围均在 $0$ 到 $Q$（含）之间。东西向街道对应网格线 $y = 0, y = 1, y = 2, \dots, y = Q$，南北向街道对应网格线 $x = 0, x = 1, x = 2, \dots, x = Q$，人们只能沿着这些街道移动。线与线的交点（例如 $(0, 0)$ 和 $(1, 2)$）即为路口。两个路口之间的最短距离通过曼哈顿距离衡量，即两组坐标的水平距离绝对值与垂直距离绝对值之和。

你知道 $P$ 个人的位置，他们都站在路口，并且知道每个人前进的指南针方向：北（$y$ 增加方向）、南（$y$ 减小方向）、东（$x$ 增加方向）或西（$x$ 减小方向）。如果一个人当前的移动方向是曼哈顿网格中通往某个街道路口的最短路径的一部分，则称该人正朝着那个街道路口移动。例如，如果一个人位于 $(x_0, y_0)$ 且正向北移动，那么他正朝着所有坐标为 $(x, y)$ 且 $y > y_0$ 的街道路口移动。

你认为可丽饼摊位于前往人数最多的那个路口。此外，你认为岛屿的南部和西部更有可能有可丽饼摊，因此如果有多个这样的路口，你将选择 $x$ 坐标最小的非负整数路口；如果仍有多个路口具有相同的 $x$ 坐标，则选择其中 $y$ 坐标最小的非负整数路口。你会选择哪个路口？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $P$ 和 $Q$：人数以及曼哈顿网格中 $x$ 或 $y$ 坐标的最大可能值。随后有 $P$ 行，第 $i$ 行包含两个整数 $X_i$ 和 $Y_i$（该人的当前位置，即街角）以及一个字符 $D_i$（该人前进的方向）。$D_i$ 是大写字母 $N, S, E, W$ 之一，分别代表北、南、东、西。

输出格式

对于每个测试用例，输出一行 Case #t: x y，其中 $t$ 是测试用例编号（从 $1$ 开始），$x$ 和 $y$ 是你认为可丽饼摊所在路口的水平和垂直坐标。

数据范围

$1 \le T \le 100$ $1 \le P \le 500$ $0 \le X_i \le Q$ $0 \le Y_i \le Q$ 对于所有 $i$，若 $X_i = 0$，则 $D_i \neq W$ 对于所有 $i$，若 $Y_i = 0$，则 $D_i \neq S$ 对于所有 $i$，若 $X_i = Q$，则 $D_i \neq E$ 对于所有 $i$，若 $Y_i = Q$，则 $D_i \neq N$

测试集 1（可见）：$Q = 10$ 测试集 2（隐藏）：$Q = 10^5$

样例

输入 1

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

输出 1

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

说明

在样例 1 中，只有一个人，他正从 $(5, 5)$ 向北移动。这意味着所有 $y \ge 6$ 的街角都是可丽饼摊的可能位置。在这些可能性中，我们选择 $x \ge 0$ 最小，然后 $y \ge 6$ 最小的路口。

在样例 2 中，有四个人，他们都朝着位置 $(2, 5)$ 移动。没有其他位置有同样多的人朝着它移动。

在样例 3 中，八个人中有六个人正朝着位置 $(0, 4)$ 移动。没有其他位置有同样多的人朝着它移动。