Problem B

Bey Battle

Time Limit: 4 Second

Dark Blader has returned with new tactics. They are now able to create an energy field around its blade and if any blade enters inside any of these energy fields the energy level of the Bit-beast drastically decreases. So Tyson had to avoid these energy fields and finally he has won!

I was lucky enough to be around Kenny who was analyzing the game with his PC and helping Tyson to avoid the energy field. I saw that the energy field was Square in shape and the blade was at its centre. At that instant a problem came to my mind and let me see how efficiently you can solve that problem.

There will be N points in a 2D plane. Find out the maximum size such that if you draw such size squares around each point (that point will be at the center of the square) no two squares will intersect each other (can touch but not intersect). To make the problem simple the sides of the squares will be parallel to X and Y axis.

Input:

Input contains several test cases. Each case starts with N which will be at most 10,000 except one case which will be 100,000. Then there are N lines- pairs of integers denoting the coordinate of each point. The absolute value of the integers can be at most 1,000,000. X or Y coordinate of any two points will be unequal.

Output:

Output a single line for each test case- maximum side length of square.

SAMPLE INPUT	OUTPUT FOR SAMPLE INPUT
2 0 0 2 2	2

Problemsetter: Md. Mahbubul Hasan