Background

A cat with horizontal and vertical patterns? Did you encounter it?

Meow... meow.

I don't know what kind of mental state the problem setter used to write about the background of such a problem, but I hope he can win the redance and return to OI.

Please note the special time limit of this problem.

Problem Description

The cat that Ai encountered can be treated as a plane with $n$ rectangles on it.

The coordinates of the bottom-left corner of the $i$-th rectangle are $(x_{i, 0},y_{i, 0})$, and the coordinates of the top-right corner are $(x_{i, 1}, y_{i, 1})$.

Find the distance between the two rectangles with the largest distance.

The distance between two rectangles is defined as the minimum Chebyshev distance between any pair of points where one point lies in the first rectangle and the other in the second one (including the boundaries).

Chebyshev distance: The Chebyshev distance between $(a,b)$ and $(c,d)$ is $\max(|a-c|,|b-d|)$.

Input Format

The first line contains an integer $n$, representing the number of rectangles.

In the next $n$ lines, the $i$-th line consists of four integers $x_{i,0},y_{i,0},x_{i,1},y_{i,1}$, representing the $i$-th rectangle.

Output Format

A single integer which represents the maximum distance between any two rectangles.

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

3

Hint

Constraints

This problem uses subtasks.

• Subtask 0 (15 pts): $n \leq 20$, $x_{i,0}, y_{i,0}, x_{i,1}, y_{i,1} \le 20$.
• Subtask 1 (20 pts): $n \leq 10^3$.
• Subtask 2 (25 pts): $x_{i,0} = x_{i,1}, y_{i,0} = y_{i,1}$.
• Subtask 3 (40 pts): No additional constraints.

For all test cases, it is guaranteed that $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}$.