고속도로

n개의 도시가 있는 나라에서 가장 멀리 떨어진 두 도시를 직행 고속도로로 잇는다.

고속도로는 양 끝 도시 사이에서 다른 나라를 지나가도 된다. 즉 n개의 도시 중 유클리드 거리가 가장 먼 두 도시를 찾으면 된다. 모든 도시는 한 평면 위의 점이다.

위 그림에서는 (12, 0)에 있는 도시와 (-6, 3)에 있는 도시의 유클리드 거리가 가장 멀다.

도시 n개의 좌표가 주어질 때, 두 도시로 이루어진 모든 쌍 중에서 거리가 가장 먼 쌍을 찾아라.

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

각 테스트 케이스의 첫 줄에 도시의 개수 n이 주어진다. (2 ≤ n ≤ 200,000) 이어서 n개의 줄에 각 도시의 x좌표와 y좌표가 주어진다. (-10,000,000 ≤ x, y ≤ 10,000,000) x와 y는 항상 정수이고, 같은 점에 있는 두 도시는 없다.

테스트 케이스마다 가장 먼 두 도시의 좌표를 한 줄에 출력한다. 두 점이 (x1, y1), (x2, y2)이면 x1 y1 x2 y2를 출력한다.

가장 먼 거리를 갖는 쌍이 여러 개일 수 있으므로 답은 다음과 같이 하나로 정한다. 한 쌍 안에서는 (x, y)를 사전순으로 비교해 더 작은 점을 앞에 쓴다. 그렇게 만든 네 수 (x1, y1, x2, y2)를 사전순으로 비교해 가장 작은 쌍 하나를 출력한다.