eolymp
bolt
Try our new interface for solving problems
Problems

Перекрёсток

Перекрёсток

Time limit 1 second
Memory limit 64 MiB

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

Расстоянием от города до магистралей будет расстояние от города до ближайшей из них. Правительство решило разместить магистрали так, чтобы максимальное расстояние от городов до магистралей было минимально возможным.

Напишите программу, которая по длине стороны квадрата и расположению городов найдет оптимальное расстояние и расположение магистралей.

Input data

В первой строке содержатся два целых числа: N (1 N 1000000) и K (1 K 40000) - длина стороны квадрата и количество городов соответственно. Последующие K строк содержат по два целых числа - координаты городов (от 0 до N).

Output data

В единственной строке выведите три целых числа – искомое оптимальное расстояние от самого удаленного города до ближайшей к нему магистрали, и координаты точки пересечения магистралей (перекрестка). Если оптимальных ответов несколько, выведите любой из них.

Examples

Input example #1
4 3
1 1
2 2
3 3
Output example #1
1 4 2
Author Андрей Коротков
Source 2012 XXV All-Ukrainian Informatics Olympiad, Vinnitsa, March 24 - 28, Round 2