問題文

二次元平面上に $N$ 個の点があります。 $i$ 番目の点の座標は $(X_i, Y_i)$ です。

$1 \leq i \leq N$ に対し、 $P_i$ を $i$ 番目の点とその他の点とのマンハッタン距離の最大値と最小値の差の絶対値とします。

$P_i$ の最小値、つまり、 $\min(P_1,P_2,\dots,P_N)$ を求めてください。

ただし、 $i$ 番目の点と $j$ 番目の点のマンハッタン距離は $|X_i - X_j| + |Y_i - Y_j|$ であるとします。

制約

• $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)$
• 入力はすべて整数

入力

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

出力

$P_i$ の最小値を出力してください。

サンプル

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