두 개의 직사각형 링

평면 도형으로서 링은 두 동심원 사이의 영역이다. 이 개념은 어떤 도형에도 확장할 수 있다. 예를 들어 직사각형 링은 두 직사각형 사이의 영역이다. 정확한 정의는 다음과 같다. 여기서 다루는 직사각형은 모두 축에 평행하다. 즉 네 변은 수평 또는 수직이며, 각각 왼쪽, 오른쪽, 위, 아래 변이라고 부른다. 수직 또는 수평 선분도 내부가 빈 직사각형으로 본다.

직사각형 링은 두 직사각형 $R$과 $R'$ 사이의 닫힌 영역이며, 경계를 포함한다. 이때 다음 두 조건을 모두 만족해야 한다.

1. $R'$은 $R$의 경계를 포함하여 $R$에 포함된다.
2. 다음 네 거리가 모두 같다. $R$의 위 변과 $R'$의 위 변 사이의 거리, $R$의 왼쪽 변과 $R'$의 왼쪽 변 사이의 거리, $R$의 아래 변과 $R'$의 아래 변 사이의 거리, $R$의 오른쪽 변과 $R'$의 오른쪽 변 사이의 거리.

두 번째 조건의 거리를 $R$과 $R'$이 정의하는 직사각형 링의 너비라고 한다. 아래 그림은 두 직사각형 $R$과 $R'$이 정의하는 너비 $w$의 직사각형 링 세 개를 보여준다. 첫 번째와 세 번째 그림은 두 극단적인 퇴화 사례다. 첫 번째는 $R' = R$인 경우로, 이때 $w = 0$이며 링은 $R' = R$의 경계 그 자체다. 세 번째는 $R'$이 선분인 경우로, 이때 $R$ 자체가 링이다.

평면 위의 유한한 점 집합 $P$가 주어졌을 때, $P \subset A\_1 \cup A\_2$를 만족하고 두 링의 너비 중 큰 값이 최소가 되는 두 개의 비관통 직사각형 링 $A\_1$과 $A\_2$를 찾는 프로그램을 작성하라. 두 직사각형 링이 비관통이라는 것은, 한쪽의 경계가 다른 쪽의 내부와 교차하지 않고, 한쪽의 경계가 다른 쪽의 경계와 엇갈리지 않는다는 뜻이다. 비관통 링끼리는 경계가 맞닿을 수 있다. 이때 두 경계가 만나는 모든 점은 평행한 두 변이 겹치는 구간이거나 모서리 위에 있다.

위 그림은 (a) 점 22개로 이루어진 예시 집합 $P$와 (b) $P$를 포함하면서 두 링 너비의 최댓값을 최소로 하는 최적의 비관통 직사각형 링 쌍을 보여준다.

첫 줄에 정수 $n$($1 \le n \le 300\,000$)이 주어진다. $n$은 $P$에 속한 점의 개수다. 이어지는 $n$개의 줄에는 공백으로 구분된 두 정수가 한 줄에 하나씩 주어지며, 이는 $P$의 한 점의 좌표다. 각 정수는 $-10^9$ 이상 $10^9$ 이하다. 서로 다른 두 입력 점이 같은 위치에 있는 경우는 없다고 가정해도 된다.

한 줄을 출력한다. 이 줄에는 $P$의 모든 점을 포함하는 두 비관통 직사각형 링에서, 두 링의 너비 중 큰 값이 가질 수 있는 최솟값을 정수로 쓴다.