The *lower envelope* of a set of ~n~ lines, in which the ~i~-th line has
the equation ~y_i = a_i \cdot x + b_i~, has the graphical representation
~y = \min_{i = 1}^n\{ a_i \cdot x + b_i \}~.

We call the *vertices* of a lower envelope the points that lie on the
lower envelope that are also the intersection of two different segments
in the set. Let us suppose that the lower envelope has ~k~ vertices
~p_1, p_2, \ldots, p_k~, with vertex ~p_i~ at a smaller x-coordinate
than ~p_{i + 1}~ (~1 \le i < k~). We call the *perimeter* of the lower
envelope being the sum of distances between every two consecutive
vertices of the lower envelope, formally
~p_1 p_2 + p_2 p_3 + \ldots p_{k - 1} p_k~. If the lower envelope
contains less than two vertices, we consider the *perimeter* to be ~0~.

The lower envelope is colored orange. It has three vertices ~p_1~, ~p_2~ and
~p_3~. The perimeter is denoted by the **continuous** orange segment.

You are given ~n~ lines. For each line, find the *perimeter* of the
lower envelope created by the *remaining* ~n - 1~ lines.

#### Input

The first line contains an integer ~n~ (~2 \le n \le 100\, 000~), the number of lines.

The ~i~-th out of the next ~n~ lines contains two integers ~a_i~ và ~b_i~ (~|a_i|, |b_i| \le 10^9~), the parameters of the ~i~-th line.

It is guaranteed that there are no two lines that are the same.

#### Output

Output ~n~ lines. The ~i~-th of which contains the *perimeter* of the
lower envelope made by the other ~n - 1~ lines, that is, excluding line
~i~.

Your answer is considered correct if its absolute or relative error does not exceed ~10^{-6}~.

Formally, let your answer be ~a~, and the jury's answer be ~b~. Your answer is accepted if and only if ~\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}~.

#### Scoring

Subtask 1 (~30~ points): ~n \le 100~.

Subtask 2 (~40~ points): ~n \le 1000~.

Subtask 3 (~130~ points): No additional constraints.

The total score for this problem is ~200~.

#### Sample Input 1

```
4
0 0
0 1
1 0
-1 3
```

#### Sample Output 1

```
1.0
3.0
0
0
```

#### Sample Input 2

```
5
4 21
-3 -13
1 -3
3 15
1 -1
```

#### Sample Output 2

```
9.1923881554
0.0000000000
6.1282587703
7.7781745931
7.7781745931
```

#### Notes

Below is the illustration for sample 1.

The first line has the equation ~y = 0x + 0~ colored red. Excluding this line, the lower envelope has vertices ~B~ và ~C~.

The second line has the equation ~y = 0x + 1~ colored blue. Excluding this line, the lower envelope has vertices ~A~ và ~D~.

The third line has the equation ~y = x~ colored green. Excluding this line, the lower envelope has vertices ~D~.

The fourth line has the equation ~y = -x + 3~ colored purple. Excluding this line, the lower envelope has vertices ~A~.

## Comments