모여서 파티하기 (스몰)

신이는 맨해튼처럼 격자로 이루어진 도시에 산다. 도시는 2차원 평면이고, 사람은 격자선을 따라 북, 서, 남, 동으로만 움직인다. 점 $(x_1, y_1)$에서 점 $(x_2, y_2)$까지의 거리는 $|x_1 - x_2| + |y_1 - y_2|$이다.

신이는 파티를 무척 좋아해서 이번 주 일요일에 집에서 파티를 열려고 한다. 참석자 명단은 이미 다 모았고, 이제 누구의 집에서 파티를 열지 정하는 일만 남았다.

신이는 직사각형 구역 몇 개에 사는 사람을 모두 초대했고, 초대받은 사람은 전부 참석한다고 답했다. 직사각형 구역은 $(x_1, y_1, x_2, y_2)$로 나타내고 $x_1 \le x_2$, $y_1 \le y_2$이다. 구역 안의 정수 좌표 점마다 사람이 한 명씩 산다. 그래서 구역 $(x_1, y_1, x_2, y_2)$에 사는 사람은 모두 $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$명이다.

신이는 각 구역의 좌표를 알고 있다. 파티는 참석자 중 한 명의 집에서 열어야 하고, 다른 참석자가 너무 멀리 오지 않도록 모든 참석자의 집에서 파티 장소까지의 거리 합을 가장 작게 만들려고 한다. 신이를 도와 그 집을 찾아라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 직사각형 구역의 개수 $B$가 주어진다. 이어지는 $B$개의 줄에는 각 구역의 좌표를 나타내는 네 정수 $x_1$, $y_1$, $x_2$, $y_2$가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄에 Case #t: x y d 형식으로 출력한다.

$t$는 1부터 시작하는 테스트 케이스 번호이고, $(x, y)$는 파티를 열 집의 좌표이다. 거리 합이 최소인 집이 여러 곳이면 $x$가 가장 작은 곳을 고르고, 그래도 여러 곳이면 그중 $y$가 가장 작은 곳을 고른다. $d$는 모든 참석자의 집에서 $(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$
• 한 테스트 케이스 안의 직사각형 구역은 서로 겹치지 않는다.
• 한 테스트 케이스의 참석자 수는 1명 이상 1000명 이하이다.