U681932 second

二维平面上有 $n$ 个房子，编号为 $1 \sim n$。$i$ 号房子的坐标为 $(x_i,y_i)$。 定义 $i$ 号房子与 $j$ 号房子之间的距离为 $\max(|x_i-x_j|, |y_i-y_j|)$。 你想知道，所有 $\frac{n(n-1)}{2}$ 对房子中，第二大的距离是多少？

本题单个测试点可能包含多组测试数据。 输入第一行包含一个整数 $T$，表示数据组数。对于每组数据： 第一行包含一个整数 $n$，表示房子个数。 接下来 $n$ 行中的第 $i$ 行包含两个整数 $x_i,y_i$，表示 $i$ 号房子的坐标。

对于每组数据，输出一行一个整数，表示第二大的距离。

#### 样例 1 解释 对于第一组数据： - $1$ 号房子与 $2$ 号房子之间的距离为 $\max(|0-1|,|0-2|)=2$。 - $1$ 号房子与 $3$ 号房子之间的距离为 $\max(|0-4|,|0-0|)=4$。 - $2$ 号房子与 $3$ 号房子之间的距离为 $\max(|1-4|,|2-0|)=3$。 第二大的距离为 $3$。 对于第二组数据： - $1$ 号房子与 $2$ 号房子之间的距离为 $\max(|0-0|,|0-0|)=0$。 - $1$ 号房子与 $3$ 号房子之间的距离为 $\max(|0-1|,|0-0|)=1$。 - $2$ 号房子与 $3$ 号房子之间的距离为 $\max(|0-1|,|0-0|)=1$。 第二大的距离为 $1$。 值得注意的是，两个房子的坐标可能相同，并且你无需对距离去重。 #### 数据范围 对于全部测试点：$1 \le T \le 5$，$3 \le n \le 2 \times 10^5$，$-10^9 \le x_i, y_i \le 10^9$。 | 测试点编号 | $n \le$ | $\lvert x_i \rvert, \lvert y_i \rvert \le$ | | :--------: | :-------------: | :----------------------------------------: | | $1\sim 3$ | $10^3$ | $10^9$ | | $4\sim 6$ | $2 \times 10^5$ | $100$ | | $7\sim 10$ | $2 \times 10^5$ | $10^9$ |