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.