Перекрёсток
Страна Квадроляндия представляет собой квадрат N×N клеток. Ее жители используют систему координат, в которой левый нижний угол квадрата имеет координаты (0, 0), правый верхний: (N, N). В Квадроляндии находятся K городов, каждый в точке с целыми координатами. Жители Квадроляндии перемещаются по стране параллельно осям координат. Для ускорения поездок в соседние страны правительство решило построить две скоростные автомагистрали. Автомагистрали должны быть перпендикулярными между собой и параллельными осям координат. Каждая магистраль будет соединять две противоположные стороны квадрата.
Расстоянием от города до магистралей будет расстояние от города до ближайшей из них. Правительство решило разместить магистрали так, чтобы максимальное расстояние от городов до магистралей было минимально возможным.
Напишите программу, которая по длине стороны квадрата и расположению городов найдет оптимальное расстояние и расположение магистралей.
Входные данные
В первой строке содержатся два целых числа: N (1 ≤ N ≤ 1000000) и K (1 ≤ K ≤ 40000) - длина стороны квадрата и количество городов соответственно. Последующие K строк содержат по два целых числа - координаты городов (от 0 до N).
Выходные данные
В единственной строке выведите три целых числа – искомое оптимальное расстояние от самого удаленного города до ближайшей к нему магистрали, и координаты точки пересечения магистралей (перекрестка). Если оптимальных ответов несколько, выведите любой из них.