32690번 - Starlight Express 스페셜 저지

무한히 넓은 2차원 좌표평면 위에 $N$개의 기차 역이 있다. 각 역에는 $1$번부터 $N$번까지의 번호가 붙어 있으며, $i$번 역은 $(x_i, y_i)$ 좌표에 위치해 있다. 모든 역의 좌표는 서로 다르고, 각 좌표의 절댓값은 $10^9$를 넘지 않는다.

각 기차 역에서는 그 역과 $x$좌표 또는 $y$좌표가 동일한 다른 역으로 이동할 수 있다. 그리고 일련의 이동 과정을 거쳐서 한 역에서 다른 역으로 이동할 수 있다면 두 역은 연결되어 있다고 한다.

여러분은 좌표평면 위에 정확히 하나의 역을 더 설치해서 서로 연결되어 있는 역 쌍의 수를 최대화하려고 한다. 이때, 설치하는 역의 좌표는 기존에 있는 $N$개의 역 좌표와는 모두 달라야 하며, 기존 역들과 동일한 좌표 범위 제한을 만족해야 한다. 역을 설치할 좌표를 구해보자. 가능한 좌표가 여러 개라면 그중 아무거나 출력한다.

첫째 줄에 역의 개수를 의미하는 정수 $N$이 주어진다. $(3 \le N \le 200\ 000)$

다음 $N$개의 줄에는 $i$번 역의 좌표를 의미하는 두 정수 $x_i, y_i$가 공백으로 구분되어 주어진다. 주어지는 모든 역의 좌표는 서로 다르다. $(-10^9 \le x_i, y_i \le 10^9)$

설치할 역의 $x$좌표와 $y$좌표를 의미하는 두 정수를 공백으로 구분하여 출력한다. 출력하는 역의 좌표는 이미 설치된 $N$개의 역의 좌표와 모두 달라야 하며, 각 좌표의 절댓값은 $10^9$ 이하여야 한다.

가능한 설치 좌표가 여러 개라면 그중 아무거나 출력한다.