Staying Hydrated

With online classes in full swing, it is important for Grace to take breaks and keep herself hydrated at all times. She has decided to place a water bottle in her room in the most convenient place. This means that the position of this water bottle should be close to all the places in the room where she generally hangs out, such as the study desk, bed, and coffee table, among other places.

The room is represented as a coordinate plane. The number of steps Grace needs to go from Point A to Point B equals the Manhattan distance between the two points. That is, Grace can walk only parallel to the axes of the coordinate plane, and with each step she can move one unit in any of the four directions.

Can you help her find a position in the room to keep the bottle such that the sum of steps from the bottle to all her favourite furniture pieces is minimum?

Notes:

• All the furniture (such as the study desk, bed, or coffee table) can be represented as rectangles of non-zero area in the plane with edges parallel to the axes.
• Furniture pieces can overlap, since she likes to work on her bed-table too.
• Assume that Grace can pass through the furniture while walking and does not need to go around it.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains an integer $K$, which represents the number of objects in Grace's room.

$K$ lines follow, each describing one object. The $i$-th line contains four integers, $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, $y_{i,2}$, where ($x_{i,1}$, $y_{i,1}$) is the coordinate of the bottom left corner and ($x_{i,2}$, $y_{i,2}$) is the coordinate of the top right corner of the $i$-th rectangular object.

For each test case, output one line containing Case #i: x y, where $i$ is the test case number (starting from 1) and $x$ and $y$ are coordinates of the water bottle such that the sum of steps from these coordinates to all the furniture pieces is minimum.

The bottle can lie on the floor or on top of any furniture, but it must be placed on integer coordinates only.

If multiple solutions exist, output the one with minimum $x$ coordinate; if multiple solutions have the same $x$ coordinate, output the one with minimum $y$ coordinate.

• $1 \le T \le 100$.
• $x_{i,1} < x_{i,2}$, for all $i$.
• $y_{i,1} < y_{i,2}$, for all $i$.