Meet and party (small)

Little Sin lives in a city laid out as a Manhattan grid. The city is a 2D plane, and people move only north, west, south or east 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|$.

Little Sin loves parties and wants to host one at a house this Sunday. She already has the guest list, so all that is left is choosing whose home hosts the party.

Little Sin invited everyone living in a few rectangular areas, and every invited person said yes. A rectangular area is written as $(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 integer point inside 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.

Little Sin knows the coordinates of each area. The party has to be at the home of one of the attendees, and she does not want the others to travel far, so she wants to minimize the sum of the distances from every attendee's home to the party. Help her find that home.

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

Each test case starts with a line containing the number of rectangular areas $B$. The next $B$ lines each contain four integers $x_1$, $y_1$, $x_2$, $y_2$ separated by spaces, giving the coordinates of one area.

For each test case, print one line in the format Case #t: x y d.

Here $t$ is the test case number starting from 1, and $(x, y)$ is the home that hosts the party. If several homes reach the same minimum total distance, choose the one with the smallest $x$; if several remain, choose the one among them with the smallest $y$. The value $d$ is the sum of the distances from every attendee's home to $(x, y)$.

• $1 \le T \le 10$
• $1 \le B \le 100$
• $|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 1000.