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