Problem Statement

There are $N$ houses numbered $1$ through $N$ on a two-dimensional plane. House $i$ is at $(x_i, y_i)$.

We use Chebyshev distance to calculate the distance between two houses. That is, the distance between Houses $i$ and $j$ is $\max(|x_i - x_j|, |y_i-y_j|)$.

There are $\frac{N(N-1)}{2}$ pairs formed by two different houses. For each of these pairs, we will calculate the distance between the houses, and then we will sort these distances in descending order to get a sequence of length $\frac{N(N-1)}{2}$. Find the second value from the beginning of this sequence.

Constraints

• All values in input are integers.
• $3 \leq N \leq 2 \times 10^{5}$
• $-10^{9} \leq x_i, y_i \leq 10^{9}$

Input

Input is given from Standard Input in the following format:

N
x_{1} y_{1}
\vdots
x_{N} y_{N}

Output

Print the second value from the beginning of the sequence of distances of different houses sorted in descending order.