분점 롤러코스터

에퀴로스터(Equiroaster)는 EQUInox ROller coASTER를 줄인 이름이고, 내년에 공원 옆 부지에 세울 대형 놀이기구다.

이 이름은 구조와 모양을 천문 현상에 직접 연결한 첫 롤러코스터라는 데서 왔다. 1년에 두 번, 춘분과 추분에 방문객은 특수 영상 효과를 더한 탑승을 즐긴다. 분점 탑승이 내는 광고 효과도 매우 클 것으로 본다.

기대에 맞추려면 에퀴로스터를 아주 정밀하게 지어야 한다. 선로는 동서 방향과 정확히 나란해야 한다. 선로는 주 교각 네 개가 받치는데, 남쪽 두 교각을 잇는 변과 북쪽 두 교각을 잇는 변도 똑같이 정확하게 동서 방향과 나란해야 한다.

공사 부지는 다른 놀이기구 바로 옆에 있다. 이 부지의 지질이 대형 공사에 그리 유리하지 않다고 보아 공원은 정밀 지질 조사를 맡겼다. 동서 방향(같은 말로 남북 방향)에 정확히 맞춘 격자를 부지에 투영했고, 격자점 사이 간격은 1미터다. 조사에서 각 격자점을 안정 또는 불안정으로 표시했다.

주 교각 네 개는 모두 안정한 격자점 위에 세워야 한다. 부지에 안정한 격자점이 넉넉해서 설계를 아주 크게 잡을 수 있기를 공원은 바라고 있다. 공법상 네 교각의 바닥은 완전한 정사각형을 이뤄야 거대한 무게를 안정적으로 받친다. 앞의 방향 조건 때문에 이 정사각형의 네 변은 격자축과 나란하다.

조건을 모두 지키면서 한 변에 놓인 두 교각 사이 거리를 최대로 할 때, 그 거리를 구하라.

입력은 여러 테스트 케이스로 이루어지고 파일 끝에서 끝난다. 각 테스트 케이스의 첫 줄에는 안정한 격자점의 개수 $N$이 주어진다 ($1 \le N \le 100000$). 이어지는 $N$개의 줄에는 격자점 하나의 $x$좌표와 $y$좌표가 주어진다. 격자축은 동서 방향과 남북 방향에 맞춰져 있고, 좌표는 미터 단위 정수다. 한 테스트 케이스 안의 격자점은 모두 서로 다르다. 각 좌표의 절댓값은 $10^9$ 이하다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 이 정수는 롤러코스터 한 변에 놓인 두 교각 중심 사이의 최대 거리이고, 단위는 미터다. 조건에 맞게 교각을 놓을 수 없으면 0을 출력한다.