Crab Hide and Seek

In this problem, iPig and giPi are playing a special game of hide and seek at the Big Fat Pig School. The twist is that they can only move horizontally or vertically. The Manhattan distance is used to measure the distance between any two points. That is, for two points \( (x_1, y_1) \) and \( (x_2, y_2) \), their distance is given by:

$$ d((x_1,y_1),(x_2,y_2)) = |x_1 - x_2| + |y_1 - y_2| $$

The school has \( N \) secret locations. At the beginning, a starting location is chosen from these \( N \) points. iPig stays at the starting location while giPi escapes within 30 seconds (and giPi will not stay in the same place). iPig then looks for giPi by moving along the shortest Manhattan path until he finds her.

Since iPig is very lazy, he always moves along the shortest path. Moreover, he chooses his starting point carefully: among the \( N \) secret locations, he wishes to choose a point such that the difference between the largest and the smallest distances (from that chosen point to every other point) is minimized. In other words, for a chosen point \( P \), let \( d_{min}(P) \) be the minimum Manhattan distance from \( P \) to any other point, and \( d_{max}(P) \) be the maximum such distance. iPig's goal is to choose a point that minimizes \( d_{max}(P) - d_{min}(P) \).

Your task is to compute this minimal difference.

inputFormat

The first line contains an integer \( N \) (\( N \ge 2 \)), the number of secret locations.

The following \( N \) lines each contain two integers \( x \) and \( y \), representing the coordinates of a secret location.

outputFormat

Output a single integer, which is the minimal possible difference \( d_{max} - d_{min} \) over all chosen starting points.

sample

2
0 0
0 1

0