题目描述

There are a lot of great streetside food vendors in Manhattan, but without a doubt, the one with the tastiest food is the Code Jam Crepe Cart!

You want to find the cart, but you do not know where it is, except that it is at some street intersection. You believe that people from across Manhattan are currently walking toward that intersection, so you will try to identify the intersection toward which the most people are traveling.

For the purposes of this problem, Manhattan is a regular grid with its axes aligned to compass lines and bounded between 0 and $\mathbf{Q}$, inclusive, on each axis. There are west-east streets corresponding to gridlines $y = 0$, $y = 1$, $y = 2$, $\cdots$, $y = \mathbf{Q}$ and south-north streets corresponding to gridlines $x = 0$, $x = 1$, $x = 2$, $\cdots$, $x = \mathbf{Q}$, and people move only along these streets. The points where the lines meet — e.g., $(0, 0)$ and $(1, 2)$ — are intersections. The shortest distance between two intersections is measured via the Manhattan distance — that is, by the sum of the absolute horizontal difference and the absolute vertical difference between the two sets of coordinates.

You know the locations of $\mathbf{P}$ people, all of whom are standing at intersections, and the compass direction each person is headed: north (increasing $y$ direction), south (decreasing $y$ direction), east (increasing $x$ direction), or west (decreasing $x$ direction). A person is moving toward a street intersection if their current movement is on a shortest path to that street intersection within the Manhattan grid. For example, if a person located at $(x_0, y_0)$ is moving north, then they are moving toward all street intersections that have coordinates $(x, y)$ with $y > y_0$.

You think the crepe cart is at the intersection toward which the most people are traveling. Moreover, you believe that more southern and western parts of the island are most likely to have a crepe cart, so if there are multiple such intersections, you will choose the one with the smallest non-negative $x$ coordinate, and if there are multiple such intersections with that same $x$ coordinate, the one among those with the smallest non-negative $y$ coordinate. Which intersection will you choose?

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case starts with one line containing two integers $\mathbf{P}$ and $\mathbf{Q}$: the number of people, and the maximum possible value of an $x$ or $y$ coordinate in Manhattan, as described above. Then, there are $\mathbf{P}$ more lines. The $i$-th of those lines contains two integers $\mathbf{X}_i$ and $\mathbf{Y}_i$, the current location (street corner) of a person, and a character $\mathbf{D}_i$, the direction that person is headed. $\mathbf{D}_i$ is one of the uppercase letters N, S, E, or W, which stand for north, south, east, and west, respectively.

输出格式

For each test case, output one line containing Case #t: x y, where $t$ is the test case number (starting from 1) and $x$ and $y$ are the horizontal and vertical coordinates of the intersection where you believe the crepe cart is located.

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

提示

Sample Explanation

In Sample Case #1, there is only one person, and they are moving north from $(5, 5)$. This means that all street corners with $y \geqslant 6$ are possible locations for the crepe cart. Of those possibilities, we choose the one with lowest $x \geqslant 0$ and then lowest $y \geqslant 6$.

In Sample Case #2, there are four people, all moving toward location $(2, 5)$. There is no other location that has as many people moving toward it.

In Sample Case #3, six of the eight people are moving toward location $(0, 4)$. There is no other location that has as many people moving toward it.

Limits

• $1 \leqslant \mathbf{T} \leqslant 100$.
• $1 \leqslant \mathbf{P} \leqslant 500$.
• $0 \leqslant \mathbf{X}_i \leqslant \mathbf{Q}$, for all $i$.
• $0 \leqslant \mathbf{Y}_i \leqslant \mathbf{Q}$, for all $i$.
• For all $i$, if $\mathbf{X}_i = 0$, $\mathbf{D}_i \neq \text{w}$.
• For all $i$, if $\mathbf{Y}_i = 0$, $\mathbf{D}_i \neq \text{s}$.
• For all $i$, if $\mathbf{X}_i = \mathbf{Q}$, $\mathbf{D}_i \neq \text{E}$.
• For all $i$, if $\mathbf{Y}_i = \mathbf{Q}$, $\mathbf{D}_i \neq \text{N}$.

Test set 1 (9 Pts, Visible)

• $\mathbf{Q} = 10$.

Test set 2 (18 Pts, Hidden)

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