Distance to the nearest point

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)$.

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$.

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.