Robot Distance

In a large warehouse, a robot can move between specified locations. The locations are given by their coordinates. The robot can only move parallel with the axes of the coordinate system. This means that when the robot wants to move from location p = (x₁, y₁) to location q = (x₂, y₂), it must go first to the place (x₂, y₁) and then to q = (x₂, y₂). Therefore, the distance that the robot travels is |x₂ − x₁| + |y₂ − y₁|. This value is called the robot distance of the locations p and q.

You are to write a program that, given a set of locations, computes the largest robot distance between two locations in the set.

Input Specification

The input contains several blocks of test cases. The first line of each case contains a single integer n (2 ≤ n ≤ 100 000), the number of locations. Each of the next n lines contains two integers x and y, the coordinates of a location (−100 000 000 ≤ x, y ≤ 100 000 000).

The input is terminated by a block with n = 0.

Output Specification

For each test case in the input, you have to output a single integer on a separate line: the largest robot distance between the locations given in the input.

Sample Input

1. 8
2. 2 3
3. 4 1
4. 7 7
5. 6 5
6. 8 10
7. 0 8
8. 4 7
9. 2 5
10. 4
11. 1 5
12. 3 0
13. 4 7
14. 3 3
15. 0

download as text file

Output for Sample Input

1. 13
2. 8

download as text file