Место встречи
Место встречи
Не следующей неделе в нашем университете состоится 1/8 финала ACM ICPC. В каждом городе расположен филиал нашего университета. Алекбер, Хидает, Шехрияр и другие участники живут в разных городах (возможно некоторые из них живут в одном городе). Наш тренер – Этибар хочет выбрать удобный город для проведения соревнования. Все участники хотят прибыть туда как можно раньше.
Из любой ячейки все ее 8 соседних достижимы за 1 единицу времени, например (x, y) достижимо из (x-1, y+1) за единицу времени. Вы можете им помочь?
n городов заданы своими координатами (x, y), где живут участники. Вам следует найти искомый город.
Входные данные
Первая строка содержит количество городов n (n ≤ 100000). Следующие n строк содержат координаты каждого из городов. Все координаты являются неотрицательными целыми числами, меньшими 10^9.
Выходные данные
Вам следует найти город, удовлетворяющий описанным условиям. Если таких городов существует несколько, то вывести город, который идет во входных данных первым. Города нумеруются с 1.
Пример
5 0 0 1 1 2 2 0 2 2 0
2