맨해튼 크레페 카트

맨해튼에는 훌륭한 길거리 음식 상인이 많지만, 의심할 여지 없이 가장 맛있는 음식을 파는 곳은 Code Jam 크레페 카트이다!

당신은 그 카트를 찾고 싶지만, 어느 거리 교차로에 있다는 것 외에는 위치를 모른다. 현재 맨해튼 전역의 사람들이 그 교차로를 향해 걷고 있다고 생각하므로, 가장 많은 사람이 이동하고 있는 교차로를 찾아내려 한다.

이 문제에서 맨해튼은 축이 방위선에 맞춰진 정규 격자이며, 각 축은 0부터 Q까지 양 끝을 포함하는 범위로 제한된다. 격자선 y = 0, y = 1, y = 2, …, y = Q에 해당하는 서쪽-동쪽 방향의 거리와 격자선 x = 0, x = 1, x = 2, …, x = Q에 해당하는 남쪽-북쪽 방향의 거리가 있으며, 사람들은 이 거리들만을 따라 이동한다. 선들이 만나는 점, 예를 들어 (0, 0)와 (1, 2)는 교차로이다. 두 교차로 사이의 최단 거리는 맨해튼 거리, 즉 두 좌표 쌍의 가로 좌표 차이의 절댓값과 세로 좌표 차이의 절댓값의 합으로 측정한다.

당신은 모두 교차로에 서 있는 P명의 위치와 각 사람이 향하는 방위, 즉 북쪽(y가 증가하는 방향), 남쪽(y가 감소하는 방향), 동쪽(x가 증가하는 방향), 또는 서쪽(x가 감소하는 방향)을 알고 있다. 어떤 사람의 현재 이동이 맨해튼 격자 안에서 어떤 거리 교차로까지 가는 최단 경로 위에 있다면, 그 사람은 그 거리 교차로를 향해 이동하고 있는 것이다. 예를 들어, ($x_{0}$, $y_{0}$)에 있는 사람이 북쪽으로 이동하고 있다면, 그 사람은 y > $y_{0}$인 좌표 (x, y)를 갖는 모든 거리 교차로를 향해 이동하고 있다.

당신은 가장 많은 사람이 이동하고 있는 교차로에 크레페 카트가 있다고 생각한다. 또한 섬의 더 남쪽이면서 더 서쪽인 지역에 크레페 카트가 있을 가능성이 가장 높다고 믿으므로, 그러한 교차로가 여러 개라면 음이 아닌 x 좌표가 가장 작은 교차로를 선택하고, 그와 같은 x 좌표를 가진 그러한 교차로도 여러 개라면 그중 음이 아닌 y 좌표가 가장 작은 교차로를 선택한다. 어느 교차로를 선택할 것인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ P ≤ 500. 모든 i에 대해, 0 ≤ $X_{i}$ ≤ Q. 모든 i에 대해, 0 ≤ $Y_{i}$ ≤ Q. 모든 i에 대해, $X_{i}$ = 0이면, $D_{i}$ ≠ W. 모든 i에 대해, $Y_{i}$ = 0이면, $D_{i}$ ≠ S. 모든 i에 대해, $X_{i}$ = Q이면, $D_{i}$ ≠ E. 모든 i에 대해, $Y_{i}$ = Q이면, $D_{i}$ ≠ N.

테스트 세트 1 (공개)

Q = 10.

테스트 세트 2 (비공개)

Q = $10^{5}$.

입력의 첫 줄에는 테스트 케이스의 수 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에서는 사람이 단 한 명뿐이며, (5, 5)에서 북쪽으로 이동하고 있다. 이는 y ≥ 6인 모든 거리 모퉁이가 크레페 카트의 가능한 위치라는 뜻이다. 그 가능성 중에서 먼저 x가 가장 낮은 ≥ 0을 선택하고, 그다음 y가 가장 낮은 ≥ 6을 선택한다.

예제 케이스 #2에서는 네 사람이 모두 위치 (2, 5)를 향해 이동하고 있다. 그만큼 많은 사람이 향해 이동하는 다른 위치는 없다.

예제 케이스 #3에서는 여덟 명 중 여섯 명이 위치 (0, 4)를 향해 이동하고 있다. 그만큼 많은 사람이 향해 이동하는 다른 위치는 없다.