Flash Mob

Jack is organizing a flash mob. Its members wander around town all day, and part of the fun is that they gather to perform whenever Jack feels like it. When the mood strikes, Jack texts every member to meet at a particular street intersection in exactly one hour. The town's streets run only north-south or east-west and are evenly spaced, forming a perfect grid like a sheet of graph paper. To keep the inconvenience small, Jack wants to choose the intersection that minimizes the total distance traveled by all members. He knows every member's current location from their phone's GPS. Your job is to find such a meeting intersection.

Each intersection is given by a pair of non-negative integers: the first coordinate is the east-west street and the second is the north-south street. Every member stands at some intersection, and members can move only along streets (north-south or east-west), so the distance between two intersections is the Manhattan (grid) distance between them.

For example, suppose 5 members are at $(3, 4)$, $(0, 5)$, $(1, 1)$, $(5, 5)$, and $(5, 5)$. If Jack gathers them at $(3, 5)$, the total number of blocks traveled is $14$, and no intersection does better — although the best intersection is sometimes not unique.

The input contains several test cases. Each test case is a sequence of integers, which may be split across one or more lines. The first integer $n$ ($1 \le n \le 1000$) is the number of members, followed by $n$ pairs of integers giving each member's location (an intersection). Every coordinate is between $0$ and $10^6$, inclusive. More than one member may stand at the same intersection. A line containing a single $0$ follows the last test case and marks the end of input.

For each test case, print one line in the form Case i: (x,y) d, where $i$ is the test case number starting from $1$, $(x,y)$ is a meeting intersection that minimizes the total number of blocks traveled, and $d$ is that minimum total.

If more than one intersection achieves the minimum total, choose the one with the smallest first coordinate; if several of those remain, choose the one among them with the smallest second coordinate.