题目背景

花纹横平竖直的猫？你遇到了？

喵……喵。

不知道出题人曾经是以什么样的精神状态写下了这样的题目背景，但我希望他能打赢复活赛回来 OI。

题目描述

哀遇到的猫可看作一个平面，上面有 $n$ 个矩形。

第 $i$ 个矩形的左下角坐标为 $(x_{i,0},y_{i,0})$，右上角坐标为 $(x_{i,1},y_{i,1})$。

求其中距离最大的两个矩形的距离。

两个矩形的距离定义为各在内部（包括四条边上）任取一点的切比雪夫距离的最小值。

切比雪夫距离：$(a,b)$ 和 $(c,d)$ 的切比雪夫距离为 $\max(|a-c|,|b-d|)$。

输入格式

第一行一个整数 $n$，表示矩形个数。

接下来 $n$ 行，第 $i$ 行四个整数 $x_{i,0}, y_{i,0}, x_{i,1}, y_{i,1}$，表示第 $i$ 个矩形。

输出格式

一行一个整数，表示任意两个矩形的距离的最大值。

5
1 2 5 2
4 0 4 4
3 3 7 3
0 5 3 5
2 1 2 6

3

提示

数据规模与约定

本题采用捆绑测试。

• Subtask 0（10 pts）：$n \leq 20$，$x_{i,0}, y_{i,0}, x_{i,1}, y_{i,1} \le 20$。
• Subtask 1（15 pts）：$n \leq 10^3$。
• Subtask 2（20 pts）：$x_{i,0} = x_{i,1}, y_{i,0} = y_{i,1}$。
• Subtask 3（55 pts）：无特殊限制。

对于所有数据，$2 \le n \le 2 \times 10^5$，$0 \le x_{i,0} \le x_{i,1} \le 10^{18}$，$0 \le y_{i,0} \le y_{i,1} \le 10^{18}$。