만나서 파티하기

리틀 신은 사람들이 격자를 따라 북쪽, 서쪽, 남쪽 또는 동쪽으로만 이동할 수 있는 2D 평면인 맨해튼 격자 도시에 산다. (x1, y1)에서 (x2, y2)까지의 거리는 |x1 - x2| + |y1 - y2|이다.

리틀 신은 파티를 무척 좋아하며 이번 일요일에 맨해튼에서 홈 파티를 열고 싶어 한다. 리틀 신은 참석할 사람들의 명단을 모았으며, 이제 누구의 집에서 파티를 열지 결정해야 한다.

리틀 신은 여러 직사각형 영역에 있는 모든 사람을 초대했고, 그 사람들은 모두 수락했다. 직사각형 영역은 (x1, y1, x2, y2)로 나타내며, x1 ≤ x2, y1 ≤ y2이다. 직사각형 영역에 사는 사람들은 그 내부의 모든 정수 좌표점에 자리한다. 따라서 직사각형 영역 (x1, y1, x2, y2)에는 총 (x2 - x1 + 1) * (y2 - y1 + 1)명의 사람이 있다.

리틀 신은 그 직사각형 영역들의 좌표를 알고 있다. 리틀 신은 참석자 중 한 사람의 집에서 파티를 열고 싶지만, 다른 모든 사람이 너무 멀리 이동해야 하는 것도 원하지 않는다. 즉, 모든 참석자의 집에서 파티 장소까지의 거리 합을 최소화하려 한다. 리틀 신을 도와줄 수 있는가?

제한

메모리 제한: 1GB.

1 ≤ T ≤ 10. |x1|, |y1|, |x2|, |y2| ≤ $10^{9}$. x1 ≤ x2, y1 ≤ y2. 한 테스트 케이스 안의 직사각형 영역들은 서로 겹치지 않는다.

테스트 세트 1 - 공개

시간 제한: 30초. 1 ≤ B ≤ 100. 1 ≤ 각 테스트 케이스의 총인원 수 ≤ 1000.

테스트 세트 2 - 비공개

시간 제한: 60초. 1 ≤ B ≤ 1000. 1 ≤ 각 테스트 케이스의 총인원 수 ≤ 1000000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 직사각형 영역의 수 B를 나타내는 정수 하나가 담긴 줄로 시작한다. 이어서 B개의 줄이 주어진다. 각 줄에는 리틀 신이 파티에 초대한 사람들이 있는 직사각형 영역의 좌표를 나타내는 4개의 정수 x1, y1, x2, y2가 주어진다.

각 테스트 케이스마다 "Case #t: x y d"을 담은 한 줄을 출력한다. 여기서 t는 테스트 케이스 번호이며(1부터 시작한다), (x, y)는 파티를 열어야 하는 사람의 집 좌표이다. 최소 총거리가 같은 위치가 여러 개라면 x가 가장 작은 위치를 선택한다. 그래도 위치가 여러 개라면 y가 가장 작은 위치를 선택한다. d의 값은 모든 참석자의 집에서 점 (x, y)까지의 거리 합이다.