Interesting Couple

Time limit2sMemory limit2048 MB

Summary

Given N points in the plane with Manhattan distance, find the smallest p(i, j) among pairs whose distance d(i, j) is no more than p(i, j).

Level: Medium7 of 10
Topics: Geometry, Sorting, Segment tree
Solved: No attempts yet

Problem

You are hosting a party with $N$ guests (numbered from $1$ to $N$ ) in a large room. The party room is a 2-dimensional Cartesian space where guest $i$ stands at $(X_i, Y_i)$ . Each guest may only move horizontally or vertically within the room.

The distance between two guests $i$ and $j$ , written $d(i, j)$ , is the total horizontal and vertical distance they need to travel to reach each other: $d(i, j) = |X_i - X_j| + |Y_i - Y_j|$ .

The privacy value of two guests $i$ and $j$ , written $p(i, j)$ , is the smallest $\min(d(i, k), d(j, k))$ over all $k$ with $k \ne i$ and $k \ne j$ . In other words, it is decided by how close each of them is to their nearest other guest.

A pair of guests $i$ and $j$ is an interesting couple if $p(i, j) \ge d(i, j)$ .

Find the minimum value of $p(i, j)$ among all interesting couples.

Input

The first line contains an integer $N$ ( $3 \le N \le 100000$ ). Each of the next $N$ lines contains two integers $X_i$ and $Y_i$ ( $0 \le X_i, Y_i \le 10^9$ ). No two guests stand at the same location, that is, $(X_i, Y_i) \ne (X_j, Y_j)$ for $1 \le i < j \le N$ .

Under the given constraints, an interesting couple always exists.

Output

Output one integer: the minimum value of $p(i, j)$ among all interesting couples.

Examples4

Example 1
Input
```
4
3 2
6 4
3 4
4 7
```
Expected output
```
3
```
Example 2
Input
```
3
4 6
8 6
6 4
```
Expected output
```
4
```
Example 3
Input
```
5
1 5
2 5
11 5
12 5
20 5
```
Expected output
```
8
```
Example 4
Input
```
5
4 4
4 3
4 5
3 4
5 4
```
Expected output
```
1
```