The developers of the e-Lite game made it possible for each player to adjust the parameters of his spaceship as he wants. Initially each player has a spaceship with n empty slots on its body. The player can either put up a jet engine in a slot or use this slot for a cargo module. Each slot can be used for an engine of a specific type, i.e., with a certain direction and power.

The spaceship’s controlling system is designed so that all the engines can be either simultaneously turned on at full power or simultaneously turned off. If the engines accelerate the spaceship in different directions, it can happen that the installation of all the engines imparts to the spaceship a smaller acceleration than the installation of only a part of them. That is why a player should think where to install engines to get the maximum acceleration.

The first line contains the number n (1 ≤ n ≤ 1 000) of empty slots on the spaceship’s body. The i-th of the following n lines contains integers x_i and y_i (−10⁶ ≤ x_i, y_i ≤ 10⁶), which are the coordinates of the vector of acceleration imparted to the ship by the i-th engine.

For each i from 1 to n, output in a separate line the value of the maximum acceleration of a ship with exactly i engines. The absolute or relative error of each answer should not exceed 10⁻⁶.