Matcom Online Grader

El profesor de Geometría Computacional enseñó en su última clase la distancia Manhattan al grupo de Fito. Al terminar la clase orientó la siguiente tarea:
“Dado N puntos en el plano, determinar por cada punto otro que esté lo más alejado posible”
Como Fito inventó una nueva enfermedad para quedarse en casa jugando en su PC, ahora no sabe cómo resolver la tarea y te pide que lo ayudes.
Nota : La distancia Manhattan entre un punto Pa y otro Pb se calcula como |Xa - Xb| + |Ya – Yb|, donde |x| representa el valor absoluto de x.

Input

La primera línea de la entrada contiene un entero positivo N (2 <= N <= 4 * 10 ⁵ ) – el número de puntos en el plano. Cada una de las siguientes N líneas describen los puntos con dos enteros X e Y separados por espacio, donde 0 <= |X|, |Y| <= 10 ⁷ . No existen dos puntos con las mismas coordenadas .

Output

N enteros positivos, uno por cada línea. El i-ésimo número es el índice del punto que está más alejado del i-ésimo punto de la entrada. Si más de un punto cumple con la condición, imprima el de menor índice.

Sample test(s)