该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Cats or dogs?

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

Frank is doing a research on how animals make humans closer. To describe the distance of two people $A$ and $B$ about an animal, he creates a formula: $dis_{A,B} = |x_a - x_b|$ if $A$ has a favorability $x_a$ for this animal and $B$ has a favorability $x_b$ for the same kind animal. And then he starts from the most common animals: dogs and cats.

After a long and difficult statistical investigation, he surveyed $n$ people about their favorability $x_i$ for cats and their favorability $y_i$ for dogs. He quickly finds that it is easy to calculate the maximum distance about cats or dogs among these people. For example, if he needs to find the maximum distance about cat, he just need to find the maximum $x_{max}$ and the minimum $x_{min}$, then the maximum distance among these people is $|x_{max} - x_{min}|$.

For further research, he wants to find the maximum distance about both cats and dogs, so he improvs the formula: $dis_{A,B} = min(|x_a - x_b|,|y_a-y_b|)$ if $A$ has a favorability $x_a$ for cats and $y_a$ for dogs and $B$ has a favorability $x_b$ for cats and $y_b$ for dogs.

Now, Frank is going to find the maximum distance among these $n$ people. It seems very easy too, so Frank gives this problem to you.

Input

The first line contains one integer $n(2\leq n \leq 10^5)$.

In the following $n$ lines, each line contains two integers $x_i,y_i(0\leq x_i,y_i \leq 10^9)$ denoting the favorability $x_i$ for cats and $y_i$ for dogs.

Output

Print a single integer, denoting the answer to the question.

3
0 3
3 1
4 10

4