Meet and Party (Large)

Sin lives in a city laid out as a grid. The city is a 2D plane, and people move only north, south, east or west along the grid lines. The distance from $(x_1, y_1)$ to $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.

Sin wants to throw a house party this Sunday. The guest list is already settled, so all that is left is choosing whose home hosts the party.

Sin picked a few rectangular areas and invited everyone living inside them, and every invited person said yes. A rectangular area is given by four integers $(x_1, y_1, x_2, y_2)$ with $x_1 \le x_2$ and $y_1 \le y_2$. One person lives at every lattice point of the area, so the area $(x_1, y_1, x_2, y_2)$ holds $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$ people.

The party has to be held at the home of one of the attendees. Sin wants to minimize the sum of the distances every attendee walks from home to the party. Find that home.

The first line contains the number of test cases $T$. The first line of each test case contains the number of rectangular areas $B$. Each of the next $B$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$ separated by spaces, the coordinates of a rectangular area of people Sin invited.

For each test case, print one line in the form "Case #t: x y d", where $t$ is the test case number starting from 1, $(x, y)$ is the home that hosts the party, and $d$ is the sum of the distances every attendee walks to that home.

If several homes give the same minimum sum, pick the one with the smallest $x$. If several still remain, pick the one with the smallest $y$ among them.

• $1 \le T \le 10$
• $1 \le B \le 1000$
• $|x_1|, |y_1|, |x_2|, |y_2| \le 10^9$
• $x_1 \le x_2$, $y_1 \le y_2$
• The rectangular areas within one test case do not overlap.
• The total number of people in one test case is at least $1$ and at most $10^6$.