题目描述

给定一个二维平面上的 $N$ 个不同点。第 $i$ 个点 $(1 \leq i \leq N)$ 的坐标为 $(x_i,y_i)$。

我们定义两个点 $i$ 和 $j$ 之间的距离为 $min(|x_i-x_j|, |y_i-y_j|)$：$x$ 坐标差和 $y$ 坐标差的较小值。

找出两个不同点之间的最大距离。

约束条件

• $2 \leq N \leq 200000$
• $0 \leq x_i, y_i \leq 10^9$
• $(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$

输出

输出一个整数表示两个不同点之间的最大距离。

示例输入 1

3
0 3
3 1
4 10

示例输出 1

4

点 1 和点 2 之间的距离、点 1 和点 3 之间的距离、点 2 和点 3 之间的距离分别为 2、4、1，因此输出为 4。

示例输入 2

4
0 1
0 4
0 10
0 6

示例输出 2

0

示例输入 3

8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

示例输出 3

801