Plant Watering

"A weed is but an unloved flower." — Ella Wheeler Wilcox

In the town of Iași, everyone loves flowers. However, since people are poor, they can only afford one flower and one sprinkler per person. Flowers can be represented as points in a 2-dimensional plane, the $i$-th person's flower being at coordinates $(x_i, y_i)$. When placing a sprinkler at the real coordinates $(X, Y)$, with a radius of $R$, it will water all the flowers at coordinates $(x,y)$ that have the manhattan distance to the sprinkler strictly smaller than $R$ (i.e. $|X-x| + |Y-y| < R$ needs to hold).

Every person wants to set the radius of their sprinkler as big as possible, but they want to place it in such a way that it waters only their flower.

Task

Determine, for each person, the greatest radius $R$ such that they can place a sprinkler of that radius that waters their flower and no other flower.

Input data

The first line contains an integer $n$ — the number of flowers (and people respectively).

The $(i+1)$-th line ($1 \leq i \leq n$) contains two integers separated by a space, $x_i$ and $y_i$, representing the coordinates of the $i$-th person's flower.

Output data

On the $i$-th line, output a real number representing the answer for the $i$-th person. The answer will be considered correct if its absolute or relative error doesn't exceed $10^{-9}$. If the radius can be arbitrarily large for a person, output $-1$.

Constraints and clarifications

• $1 \le n \le 500$
• $-10^9 \le x_i, y_i \le 10^9$
• The points in the input are pairwise distinct.

Example

stdin

5
5 5
5 6
6 5
4 5
5 4

stdout

1
-1
-1
-1
-1