채굴 센터 위치 정하기

외딴 무인 지역에서 여러 개의 후보 채굴 지점이 조사되었고, 이제 채굴 센터(Mining Center)를 어디에 둘지 정해야 합니다. 로봇은 각 채굴 지점에서 채굴 센터까지 광물을 운반하지만, 그림에 표시된 미리 정해진 격자선(grid line)을 따라서만 이동할 수 있습니다. 따라서 두 지점 사이의 이동 비용은 두 점의 직각 거리(맨해튼 거리, rectilinear / Manhattan distance)와 같습니다. 채굴 센터에서 각 채굴 지점까지의 거리 중 최댓값이 가능한 한 작아지도록 센터의 위치를 정해야 합니다.

정확히 말하면, $n$개의 채굴 지점의 좌표 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$가 주어집니다. 채굴 센터의 정수 좌표 $(x_0, y_0)$를

$\max_{1 \le i \le n} \left( |x_i - x_0| + |y_i - y_0| \right)$

가 최소가 되도록 정하세요. 여기서 $(x_0, y_0)$와 $(x_i, y_i)$ 사이의 직각 거리는 $|x_i - x_0| + |y_i - y_0|$입니다.

이 최솟값을 달성하는 위치가 여러 개라면, 원점 $(0, 0)$에 가장 가까운 위치, 즉 $\sqrt{x_0^2 + y_0^2}$가 가장 작은 위치를 고르세요. 유클리드 거리까지 같은 위치가 여러 개라면, 좌표쌍 $(x_0, y_0)$가 사전순으로 가장 작은 것을 고르세요. 즉 $x_0$가 더 작은 것을 먼저, $x_0$가 같으면 $y_0$가 더 작은 것을 고릅니다.

모든 좌표는 정수입니다. 좌표 값은 매우 클 수 있으므로(수백만 이상), 후보 위치를 전부 훑는 완전 탐색으로는 풀 수 없습니다.

첫 줄에는 테스트 케이스의 개수 $T$가 주어집니다.

이어지는 $T$개의 줄에는 각각 하나의 테스트 케이스가 주어집니다. 각 줄은 채굴 지점의 개수 $n$으로 시작하고, 그 뒤에 각 지점의 좌표 $x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n$이 이어집니다. 모든 좌표는 정수이며, 값이 매우 클 수 있습니다(수백만 이상).

각 테스트 케이스마다 한 줄에

LOCATION x0 y0

를 출력하세요. 여기서 $(x_0, y_0)$는 위 규칙에 따라 정해진 채굴 센터의 정수 좌표입니다. 즉 가능한 직각 거리의 최댓값이 최소, 그다음 원점까지의 유클리드 거리가 최소, 그다음 사전순으로 가장 작은 $(x_0, y_0)$입니다.