Distance to the nearest point

Time limit2sMemory limit512 MB

Summary

For each of N points, report the Manhattan distance to the nearest other point.

Level: Hard8 of 10
Topics: Geometry, Divide and conquer, Sorting
Solved: No attempts yet

Problem

The distance $D(A, B)$ between two points $A(x_1, y_1)$ and $B(x_2, y_2)$ is defined as follows.

$D(A, B) = |x_1 - x_2| + |y_1 - y_2|$

You are given $N$ points $A_1, A_2, \dots, A_N$ . For each point $A_i$ , find the closest point $A_j$ among the others and report the distance $D(A_i, A_j)$ .

Input

The first line contains the number of points $N$ ( $2 \le N \le 2 \times 10^5$ ).

Each of the next $N$ lines contains the coordinates $x$ and $y$ of a point $A_i$ , separated by a space ( $-10^7 \le x, y \le 10^7$ ). All coordinates are integers. Two or more points may have exactly the same coordinates, and the distance between such a pair is $0$ .

Output

For $A_1$ through $A_N$ , in the order given in the input, print the distance from that point to its closest point, one per line.

Examples4

Example 1
Input
```
4
0 0
0 1
1 0
1 1
```
Expected output
```
1
1
1
1
```
Example 2
Input
```
4
0 0
1 100
4 3
100 2
```
Expected output
```
7
100
7
97
```
Example 3
Input
```
4
0 0
3 3
1 100
100 1
```
Expected output
```
6
6
99
99
```

Example 4

Input

2
-10000000 -10000000
10000000 10000000

Expected output

40000000
40000000