Problem Statement

There are $N$ points on a two-dimensional plane. The coordinates of the $i$-th point are $(X_i, Y_i)$.

For $1 \leq i \leq N$, let $P_i$ be the absolute value of the difference between the maximum and the minimum of the Manhattan distances between the $i$-th point and the other points.

Find the minimum value of $P_i$, that is, $ \min(P_1,P_2,\dots,P_N) $.

Here, the Manhattan distance between the $i$-th point and the $j$-th point is $ |X_i - X_j| + |Y_i - Y_j| $.

Constraints

• $ 2 \leq N \leq 2 \times 10^5 $
• $ 1 \leq X_i, Y_i \leq N $
• $ (X_i, Y_i) \neq (X_j, Y_j)\ (i \neq j) $
• All inputs are integers.

Input

$N$
$X_1\ Y_1$
$X_2\ Y_2$
$\vdots$
$X_N\ Y_N$

Output

Output the minimum value of $P_i$.

Sample

4
1 1
1 2
3 2
4 4

1

3
1 1
2 2
3 3

0

12
1 1
5 7
5 4
9 9
10 5
2 11
6 1
9 2
1 9
4 11
11 12
9 5

8