Host Place#5497
Next week ACM ICPC final contest is held in our university. There is branch of our university in each city. Alekber, Hidayet, Shehriyar and other our heroes are living in different cities (maybe some of them are living in the same city). Our coach – Etibar wants to choose a good city for hosting this contest. All participants have to be there in time.
From any given cell, all adjacent cells are reachable in unit of time, e.g. can be reached from (x-1, y+1) in one unit of time. Could you help him?
You are given cities where participants are living . Your task is to find which city is appropriate.
First line contains the number of cities (n \le 100000). The following lines contain the coordinates of each city. All coordinates are nonnegative integers and less than 10^9.
Your task is to find such a city that satisfies the conditions mentioned above. If there are more than one correct solution, print city which is coming first in input. Cities are numbered from .
Example 1