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