Given two vectors, a = ( x_a, y_a ), b = ( x_b, y_b ), their dot product is defined as follows:
dp( a, b ) = x_a*x_b + y_a*y_b.

Given N vectors in the plane, find a pair for each of them (among those given in the input) such that the dot product of the vector and its pair is maximal. You may pair a vector with itself too.

Input

The first line of input contains a single integer N ( 1 <= N <= 200000 ).
Each of the next N lines contain a pair of real numbers, x_i and y_i (0 <= |x_i|, |y_i| <= 100000)_, representing the i-th vector. x_i and y_i will be rounded to 3 decimal places.

Output

Output N lines, i-th one containing the maximal dot product for the i-th vector from the input rounded to 3 decimal places.

Example

Input: 

4
0.000 1.000
0.000 2.000
1.000 1.000
0.000 0.000

Output:
 
2.000
4.000
2.000
0.000

Explanation: Pair the first vector with the second, the second with itself, third with itself or with the second, and the last one with any of them.