Locate Mining Center

Scientists have identified many possible excavation sites in a remote, deserted area and now need to decide where to place the Mining Center. Robots carry the mined material from each excavation site to the mining center, but they may travel only along the prespecified grid lines shown in the figure, so the travel cost between two points equals their rectilinear (Manhattan) distance. The mining center should be placed so that the maximum distance from the center to any excavation site is as small as possible.

Formally, you are given the coordinates of $n$ excavation sites $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$. Choose integer coordinates $(x_0, y_0)$ for the mining center so that

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

is minimized, where the rectilinear distance between $(x_0, y_0)$ and $(x_i, y_i)$ is $|x_i - x_0| + |y_i - y_0|$.

If several locations achieve this minimum, choose the one closest to the origin $(0, 0)$, i.e. the one that minimizes $\sqrt{x_0^2 + y_0^2}$. If several locations are still tied on that Euclidean distance, choose the lexicographically smallest coordinate pair $(x_0, y_0)$: smaller $x_0$ first, and if $x_0$ ties, smaller $y_0$.

All coordinates are integers. Coordinate values can be large (in the millions), so a brute-force scan over candidate positions will not work.

The first line contains an integer $T$: the number of test cases.

Each of the next $T$ lines describes one test case. The line begins with $n$, the number of excavation sites, followed by the coordinates of the sites: $x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n$. All coordinates are integers and may be large (millions or more).

For each test case, print a single line

LOCATION x0 y0

where $(x_0, y_0)$ are the integer coordinates of the mining center selected by the rules above: the minimum possible maximum rectilinear distance, then the smallest Euclidean distance to the origin, then the lexicographically smallest $(x_0, y_0)$.