맨해튼 크레페 카트 timer 20s memory 1024MB

맨해튼에는 훌륭한 길거리 음식 노점이 많지만, 의심의 여지 없이 가장 맛있는 곳은 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₀, y₀)에 있는 사람이 북쪽으로 움직이고 있다면, y > y₀를 만족하는 모든 (x, y) 교차로를 향해 이동하고 있는 것이다.

당신은 크레페 카트가 가장 많은 사람들이 향하고 있는 교차로에 있다고 생각한다. 또한 당신은 섬의 더 남쪽, 더 서쪽에 있는 곳일수록 카트가 있을 가능성이 높다고 믿는다. 그래서 그런 교차로가 여러 개라면, 음이 아닌 x 좌표가 가장 작은 것을 고르고, 그 x 좌표까지 같은 것이 여러 개라면 그중 음이 아닌 y 좌표가 가장 작은 것을 고르기로 한다. 당신은 어떤 교차로를 선택하겠는가?