Maximal Chebyshev Distance Between Rectangles

Given a set of n rectangles on a plane, where the i-th rectangle is defined by its bottom-left corner ( (x_{i,0}, y_{i,0}) ) and top-right corner ( (x_{i,1}, y_{i,1}) ), your task is to determine the maximum distance between any two rectangles.

The distance between two rectangles is defined as the minimum Chebyshev distance over all pairs of points (one taken from each rectangle, including the boundaries).

The Chebyshev distance between two points ( (a,b) ) and ( (c,d) ) is given by:
( \max(|a-c|,,|b-d|) ).

inputFormat

The first line contains an integer ( n ), the number of rectangles.

Each of the following ( n ) lines contains four integers ( x_{i,0} ), ( y_{i,0} ), ( x_{i,1} ), ( y_{i,1} ) describing a rectangle.

outputFormat

Output a single integer representing the maximal distance between any two rectangles.

sample

2
0 0 1 1
2 2 3 3

1