Thanks to the development of faster-than-light propulsion, spaceships from the planet Bytotia have begun colonizing other planets in the observable universe. A total of $n$ planets have been colonized, and for effective communication, a communication satellite with a transmitter must be placed in orbit around each of them.

The position of a planet in the universe can be described by two coordinates $(x, y)$ (the universe can thus be modeled as a plane). The transmitter power required for faster-than-light communication between planets at coordinates $(x_1, y_1)$ and $(x_2, y_2)$ is equal to the distance between them, i.e., $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$. Each satellite must be equipped with a transmitter with enough power to communicate simultaneously with all other planets, which means a power equal to the sum of the distances between the transmitter and all other planets.

The Bytotian government wants to know the required power for each transmitter, and your task is to calculate it. Since this data is only intended to help estimate the cost of the satellites, it does not need to be very precise — it is sufficient that each calculated power differs by at most 0.1% (one-tenth of a percent) from the actual value.

Input

The first line of the input contains an integer $n$ ($2 \le n \le 100\,000$) representing the number of planets. The next $n$ lines describe the planets; the $i$-th of these lines contains two integers $x, y$ ($-10^6 \le x, y \le 10^6$) representing the coordinates of the $i$-th planet.

You may assume that no two planets have the same position.

Output

You must output exactly $n$ lines. Let $s_i$ be the sum of the distances from the $i$-th planet to all others. In the $i$-th line of the output, you must print a real number $s'_i$ in decimal format (not in scientific notation). The result will be accepted if, for every $i$, the following condition is satisfied: $$|s_i - s'_i| \le \frac{s_i}{1000}.$$

Examples

Input 1

4
-1 0
0 0
3 3
-1 1

Output 1

7.001
6.655
13.71477
6.885

Note

The exact and rounded-to-three-decimal-places sums of distances for the consecutive planets are $7$, $1 + 4\sqrt{2} \approx 6.657$, $5 + 4\sqrt{2} + 2\sqrt{5} \approx 13.715$, and $1 + \sqrt{2} + 2\sqrt{5} \approx 6.886$.

Evaluation tests

The evaluation tests are as follows: 1. $n = 25$; planets have coordinates $(i, j)$ for $-2 \le i, j \le 2$. 2. $n = 100\,000$; planets have coordinates $(2i, i)$ for $0 \le i < n$.

Subtasks