수분 유지하기

온라인 수업이 한창인 가운데, Grace가 휴식을 취하고 항상 수분을 충분히 섭취하는 것이 중요하다. 그녀는 방에서 가장 편리한 장소에 물병을 두기로 했다. 이는 이 물병의 위치가 책상, 침대, 커피 테이블을 비롯하여 그녀가 평소에 시간을 보내는 방 안의 모든 장소와 가까워야 한다는 뜻이다.

방은 좌표평면의 형태로 표현된다. Grace가 점 A에서 점 B로 가는 데 필요한 걸음 수는 2 점 사이의 맨해튼 거리와 같다. 즉, Grace는 좌표평면의 축과 평행하게만 걸을 수 있으며, 한 걸음마다 네 방향 중 하나로 한 단위만큼 이동할 수 있다.

물병에서 그녀가 좋아하는 모든 가구까지의 걸음 수의 합이 최소가 되도록 물병을 둘 방 안의 위치를 찾는 것을 도와줄 수 있는가?

참고:

• 모든 가구(책상, 침대, 커피 테이블 등)는 평면에서 넓이가 영이 아니고 변이 축과 평행한 직사각형으로 표현할 수 있다.

• 그녀는 침대용 테이블에서도 일하는 것을 좋아하므로 가구들이 서로 겹칠 수도 있다.

• Grace는 걸을 때 가구를 피해 돌아갈 필요 없이 그대로 통과할 수 있다고 가정한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $\mathbf{x_{i,1}} \lt \mathbf{x_{i,2}}$. 모든 $i$에 대해 $\mathbf{y_{i,1}} \lt \mathbf{y_{i,2}}$.

테스트 세트 1

시간 제한: 40초. $1 \le \mathbf{K} \le 20$. 모든 $i$에 대해 $-100 \le \mathbf{x_{i,1}},\mathbf{x_{i,2}},\mathbf{y_{i,1}},\mathbf{y_{i,2}} \le 100$.

테스트 세트 2

시간 제한: 90초. $1 \le \mathbf{K} \le 10^5$ 모든 $i$에 대해 $-10^9 \le \mathbf{x_{i,1}},\mathbf{x_{i,2}},\mathbf{y_{i,1}},\mathbf{y_{i,2}} \le 10^9$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 Grace의 방에 있는 물체의 수를 나타내는 정수 $\mathbf{K}$이 주어진다. 이어지는 $\mathbf{K}$개의 줄에는 각각 하나의 물체에 대한 설명이 주어진다. $i$번째 줄에는 네 정수 $\mathbf{x_{i,1}}$, $\mathbf{y_{i,1}}$, $\mathbf{x_{i,2}}$, $\mathbf{y_{i,2}}$가 주어지며, ($\mathbf{x_{i,1}}$, $\mathbf{y_{i,1}}$)는 $i$번째 직사각형 물체의 왼쪽 아래 꼭짓점 좌표를 나타내고 ($\mathbf{x_{i,2}}$, $\mathbf{y_{i,2}}$)는 오른쪽 위 꼭짓점 좌표를 나타낸다.

각 테스트 케이스마다 Case #$i$: $x$ $y$를 포함하는 한 줄을 출력한다. 여기서 $i$는 테스트 케이스 번호(1부터 시작)이고, $x$와 $y$는 해당 좌표에서 모든 가구까지의 걸음 수의 합이 최소가 되도록 하는 물병의 좌표이다. 물병은 바닥이나 어떤 가구 위에도 놓일 수 있지만, 반드시 정수 좌표에만 놓아야 한다. 해가 여러 개라면 x 좌표가 최소인 것을 출력하고, x 좌표가 같은 해가 여러 개라면 y 좌표가 최소인 것을 출력한다.

예제 케이스 #1에서 Grace는 물병을 좌표 ($1$, $3$)에 놓을 수 있다. 이 위치는 첫 번째 물체에서 $2$걸음, 두 번째 물체에서 $1$걸음, 세 번째 물체에서 $0$걸음 떨어져 있으며, 이에 따라 한 점에서 각 물체까지의 걸음 수의 가능한 최소 합은 $3$가 된다.

예제 케이스 #2에서 물병은 물체 자체의 어느 곳에나 놓일 수 있지만, 좌표 ($0$, $0$)가 최소 x 좌표와 최소 y 좌표에 해당한다.