Host Place
Next week ACM ICPC 1/8 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 8 adjacent cells are reachable in 1 unit of time, e.g. (x, y) can be reached from (x-1, y+1) in one unit of time. Could you help him?
You are given n cities where participants are living (x, y). Your task to find which city can be appropriate.
Input
First line contains the number of cities n (n ≤ 100000). The following n lines contain the coordinates of each city. All coordinates are nonnegative integers and less than 10^9.
Output
Your task is to find such city satisfy the conditions which is mentioned above. If there are more than one correct solution, print city which is coming first in input. Cities are numbered from 1.