На футбольном стадионе Рамакана беспорядки! Разъяренные болельщики выбежали на поле и полиция оказалась в затруднительном положении. Поле можно представить как квадрат с двумя противоположным вершинами в точках (0,0) и (10⁵, 10⁵). Считается, что внутренние точки квадрата и его стороны расположены внутри поля, а всё остальное находится за его пределами.

Вначале на поле N болельщиков. Для каждого болельщика дана его скорость, целое число v_i, а также его целочисленные координаты (x_i, y_i). Через одну секунду болельщик может быть в любой точке (x_i + p, y_i + q), где 0 ≤ |p| + |q| ≤ v_i. И p, и q должны быть целыми числами.

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

Андрей, молодой и перспективный полицейский, послал беспилотник, чтобы заснять беспорядки с воздуха. Фотоаппарат беспилотника работает следующим образом:

1. Он выбирает три точки с целочисленными координатами, такие, что есть вероятность, что через секунду там появится болельщик. Они не должны лежать на одной прямой, иначе фотоаппарат не сработает. Гарантируется, что не все начальные позиции болельщиков будут на одной прямой.
2. Фотоаппарат фокусируется на трех точках и создает круг, проходящий через эти три точки. Через секунду делается снимок (через секунду после исходного состояния).
3. Всё, что лежит на границе круга или внутри него на момент фотографирования (через секунду после фокусирования точек) будет на снимке.

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

Гарантируется что радиус оптимальной окружности в тестах не превзойдет 10¹⁰.