Разработчики игры e-Lite позаботились о том, чтобы каждый игрок мог настроить параметры своего космического корабля по своему желанию. Изначально игроку даётся корпус корабля с n свободными слотами. Можно либо установить в слот реактивный двигатель, либо использовать этот слот под грузовой отсек. В каждый слот можно установить только двигатель конкретного типа, с определённым направлением и силой тяги.

Управляющая система корабля построена так, что все двигатели могут быть либо одновременно включены на максимальную мощность, либо одновременно выключены. Заметим, что если все двигатели придают кораблю ускорение в разных направлениях, то установка их всех может дать кораблю меньшую тягу, чем установка лишь части из них. Поэтому при снаряжении своего корабля игроку придётся подумать, куда нужно поставить двигатели, чтобы добиться максимальной тяги.

В первой строке записано целое число n — количество свободных слотов на корпусе корабля (1 ≤ n ≤ 1000). В i-й из следующих n строк записаны целые числа x_i и y_i — координаты вектора ускорения, придаваемого кораблю i-м двигателем (−10⁶ ≤ x_i, y_i ≤ 10⁶).

Для каждого i от 1 до n выведите в отдельной строке величину максимального ускорения, которое может развивать корабль при установке на него ровно i двигателей. Абсолютная или относительная погрешность каждого ответа не должна превосходить 10⁻⁶.