플래시몹

잭(Jack)은 플래시몹을 준비하고 있다. 구성원들은 하루 종일 도시 곳곳을 돌아다니는데, 잭이 마음 내킬 때마다 한곳에 모여 공연을 하는 것이 이 모임의 묘미다. 마음이 내키면 잭은 모든 구성원에게 정확히 한 시간 뒤 특정 교차로에서 만나자는 문자를 보낸다. 이 도시의 길은 남북 방향 또는 동서 방향으로만 나 있고 일정한 간격으로 배치되어, 모눈종이처럼 완벽한 격자를 이룬다. 잭은 불편을 최소화하기 위해, 모든 구성원이 이동하는 거리의 합이 가장 작아지는 교차로를 고르려고 한다. 각 구성원의 현재 위치는 휴대전화 GPS로 알 수 있다. 모든 구성원의 위치가 주어질 때 이러한 만남 장소(교차로)를 찾는 것이 문제다.

각 교차로는 음이 아닌 정수 쌍으로 주어진다. 첫 번째 좌표는 동서 방향 길, 두 번째 좌표는 남북 방향 길을 나타낸다. 각 구성원은 어떤 교차로에 있으며, 길을 따라 남북 또는 동서 방향으로만 이동할 수 있으므로, 두 교차로 사이의 거리는 두 점 사이의 맨해튼(격자) 거리이다.

예를 들어 5명의 구성원이 각각 $(3, 4)$, $(0, 5)$, $(1, 1)$, $(5, 5)$, $(5, 5)$에 있다고 하자. 잭이 이들을 $(3, 5)$로 모으면 이동한 블록 수의 합은 $14$이고, 이보다 더 좋은 교차로는 없다. 다만 최적의 교차로가 유일하지 않을 수도 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수들의 나열이며, 이 정수들은 한 줄 또는 여러 줄에 걸쳐 주어질 수 있다. 첫 번째 정수 $n$ ($1 \le n \le 1000$)은 구성원의 수이고, 그 뒤에 각 구성원의 위치(교차로)를 나타내는 정수 쌍이 $n$개 이어진다. 모든 좌표는 $0$ 이상 $10^6$ 이하이다. 두 명 이상의 구성원이 같은 교차로에 있을 수 있다. 마지막 테스트 케이스 다음에는 $0$ 하나만 있는 줄이 오며, 이는 입력의 끝을 나타낸다.

각 테스트 케이스마다 한 줄을 Case i: (x,y) d 형식으로 출력한다. 여기서 $i$는 $1$부터 시작하는 테스트 케이스 번호, $(x,y)$는 이동한 블록 수의 합을 최소로 만드는 만남 교차로, $d$는 그 최소 합이다.

최소 합을 이루는 교차로가 여러 개이면 첫 번째 좌표가 가장 작은 것을 고르고, 그런 교차로가 여럿이면 그중 두 번째 좌표가 가장 작은 것을 고른다.