Перехрестя
Країна Квадроляндія представлена у вигляді квадрату розміром N×N клітинок. Її мешканці використовують систему координат, де лівий нижній кут квадрата має координати (0, 0), а правий верхній — (N, N). У Квадроляндії розташовано K міст, кожне з яких знаходиться в точці з цілими координатами. Жителі пересуваються країною, рухаючись паралельно осям координат. Для полегшення поїздок до сусідніх країн уряд вирішив побудувати дві швидкісні автомагістралі. Ці автомагістралі повинні бути перпендикулярними одна одній і паралельними осям координат, з'єднуючи протилежні сторони квадрата.
Відстань від міста до автомагістралей визначається як відстань до найближчої з них. Уряд прагне розмістити автомагістралі так, щоб максимальна відстань від будь-якого міста до найближчої автомагістралі була якомога меншою.
Напишіть програму, яка, маючи довжину сторони квадрата та розташування міст, знайде оптимальну максимальну відстань від міст до автомагістралей і координати їх перетину.
Вхідні дані
У першому рядку подано два цілі числа: N (1 ≤ N ≤ 1000000) і K (1 ≤ K ≤ 40000) — довжина сторони квадрата та кількість міст відповідно. Наступні K рядків містять по два цілі числа — координати міст (від 0 до N).
Вихідні дані
Виведіть в одному рядку три цілі числа: оптимальну максимальну відстань від найвіддаленішого міста до найближчої автомагістралі та координати точки перетину автомагістралей (перехрестя). Якщо існує кілька оптимальних рішень, виведіть будь-яке з них.