수분 보충

온라인 수업이 한창인 요즘, Grace는 쉬는 시간을 챙기고 항상 수분을 보충하는 것이 중요하다고 생각한다. 그래서 방 안에서 가장 편리한 곳에 물병을 두기로 했다. 물병은 그녀가 주로 머무는 곳, 예를 들어 책상, 침대, 커피 테이블 등 여러 장소에 가까워야 한다.

방은 좌표평면으로 나타낸다. Grace가 점 A에서 점 B로 이동하는 데 필요한 걸음 수는 두 점의 맨해튼 거리와 같다. 즉, Grace는 좌표축에 평행하게만 걸을 수 있고, 한 걸음마다 네 방향 중 하나로 1만큼 움직일 수 있다.

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

참고:

• 모든 가구(책상, 침대, 커피 테이블 등)는 좌표평면에서 변이 좌표축에 평행하고 넓이가 0이 아닌 직사각형으로 나타낼 수 있다.
• 그녀가 침대 위 테이블에서도 작업하기를 좋아하므로, 가구끼리 겹칠 수 있다.
• Grace는 가구를 통과해서 걸을 수 있으며, 가구를 돌아갈 필요가 없다고 가정한다.

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

각 테스트 케이스의 첫 줄에는 Grace의 방에 있는 물체의 수를 나타내는 정수 $K$가 주어진다.

이어서 $K$개의 줄에 각각 하나의 물체를 나타내는 정보가 주어진다. $i$번째 줄에는 네 정수 $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, $y_{i,2}$가 주어지며, ($x_{i,1}$, $y_{i,1}$)은 $i$번째 직사각형 물체의 왼쪽 아래 꼭짓점 좌표, ($x_{i,2}$, $y_{i,2}$)는 오른쪽 위 꼭짓점 좌표이다.

각 테스트 케이스마다 Case #i: x y 형식의 한 줄을 출력한다. 여기서 $i$는 테스트 케이스 번호(1부터 시작)이고, $x$와 $y$는 이 좌표에서 모든 가구까지의 걸음 수 합이 최소가 되는 물병의 좌표이다.

물병은 바닥에 놓거나 가구 위에 놓을 수 있지만, 정수 좌표에만 놓아야 한다.

최적의 해가 여러 개라면 $x$ 좌표가 가장 작은 것을 출력하고, $x$ 좌표가 같은 해가 여러 개라면 $y$ 좌표가 가장 작은 것을 출력한다.

• $1 \le T \le 100$.
• 모든 $i$에 대해 $x_{i,1} < x_{i,2}$.
• 모든 $i$에 대해 $y_{i,1} < y_{i,2}$.