eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Место встречи

Место встречи

Лимит времени 0.5 секунд
Лимит использования памяти 64 MiB

Не следующей неделе в нашем университете состоится 1/8 финала ACM ICPC. В каждом городе расположен филиал нашего университета. Алекбер, Хидает, Шехрияр и другие участники живут в разных городах (возможно некоторые из них живут в одном городе). Наш тренер – Этибар хочет выбрать удобный город для проведения соревнования. Все участники хотят прибыть туда как можно раньше.

Из любой ячейки все ее 8 соседних достижимы за 1 единицу времени, например (x, y) достижимо из (x-1, y+1) за единицу времени. Вы можете им помочь?

n городов заданы своими координатами (x, y), где живут участники. Вам следует найти искомый город.

Входные данные

Первая строка содержит количество городов n (n100000). Следующие n строк содержат координаты каждого из городов. Все координаты являются неотрицательными целыми числами, меньшими 10^9.

Выходные данные

Вам следует найти город, удовлетворяющий описанным условиям. Если таких городов существует несколько, то вывести город, который идет во входных данных первым. Города нумеруются с 1.

Пример

Входные данные #1
5
0 0
1 1
2 2
0 2
2 0
Выходные данные #1
2
Автор Mahammad Valiyev
Источник Local Contest #1 Qafqaz University by Mahammad Valiyev