Місце зустрічі
Наступного тижня в нашому університеті відбудеться 1/8 фіналу ACM ICPC. У кожному місті розташована філія нашого університету. Алекбер, Хідаєт, Шехріяр та інші учасники живуть у різних містах (можливо, деякі з них живуть в одному місті). Наш тренер, Етібар, хоче обрати зручне місто для проведення змагання. Усі учасники прагнуть прибути туди якомога швидше.
З будь-якої клітинки всі її 8 сусідів досяжні за 1 одиницю часу, наприклад, з (x-1, y+1) можна дістатися до (x, y) за одиницю часу. Чи можете ви допомогти їм?
Задано n міст, кожне з яких має координати (x, y), де живуть учасники. Вам потрібно знайти відповідне місто.
Вхідні дані
Перший рядок містить кількість міст n (n ≤ 100000). Наступні n рядків містять координати кожного з міст. Усі координати є невід'ємними цілими числами, меншими за 10^9.
Вихідні дані
Вам потрібно знайти місто, яке відповідає описаним умовам. Якщо таких міст є декілька, виведіть те, яке з'являється першим у вхідних даних. Міста нумеруються з 1.