파티 장소 정하기 (Large)

신은 바둑판처럼 생긴 도시에 산다. 도시는 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)$는 파티를 열 집의 좌표, $d$는 그 집까지 참석자 전원이 이동하는 거리의 합이다.

거리의 합이 최소인 집이 여러 곳이면 $x$가 가장 작은 집을 고른다. 그러고도 여러 곳이 남으면 그중 $y$가 가장 작은 집을 고른다.

• $1 \le T \le 10$
• $1 \le B \le 1000$
• $|x_1|, |y_1|, |x_2|, |y_2| \le 10^9$
• $x_1 \le x_2$, $y_1 \le y_2$
• 한 테스트 케이스 안의 직사각형 구역은 서로 겹치지 않는다.
• 한 테스트 케이스에 사는 사람 수의 합은 $1$ 이상 $10^6$ 이하이다.