진지한 소 술래잡기

농부 존의 소 $N$마리($1 \le N \le 1000$)가 있으며, $1$번부터 $N$번까지 번호가 매겨져 있습니다. 이 소들은 "진지한 소 술래잡기"라는 놀이를 합니다. 각 소는 목초지의 서로 다른 격자점에 서 있고, 좌표는 정수이며 $-7500 \le X \le 7500$, $-7500 \le Y \le 7500$을 만족합니다. 소들의 위치는 모든 소 쌍 사이의 거리가 서로 다르도록 배치되어 있습니다.

소들은 정해진 순서대로 차례를 진행합니다. $1$번 소가 먼저, 그다음 $2$번 소, $3$번 소, ... 순으로 진행하며, $N$번 소 다음에는 다시 $1$번 소로 돌아와 반복합니다. 이미 잡힌(태그된) 소는 건너뛰며 다시는 차례를 갖지 않습니다.

자기 차례가 된 소는 아직 놀이에 남아 있는 소들 중 가장 가까운 소에게 걸어가 그 소를 태그한 뒤 자기 자리로 돌아옵니다. 태그된 소는 즉시 놀이에서 탈락합니다. 모든 쌍의 거리가 서로 다르므로, 가장 가까운 소는 항상 유일하게 정해집니다.

놀이는 소가 한 마리만 남을 때까지 계속되며, 마지막에 남은 소가 승자가 됩니다.

농부 존은 승자를 미리 알고 싶어 합니다. 소들의 위치가 주어질 때, 어떤 소가 이기는지 구하세요.

• 첫째 줄에 소의 수 $N$이 정수로 주어집니다.
• 다음 $N$개의 줄 중 $i$번째 줄에는 $i$번 소의 위치를 나타내는 두 정수 $X$와 $Y$가 공백으로 구분되어 주어집니다.

• 승리한 소의 번호를 한 줄에 출력합니다.

소가 세 마리인 경우, $1$번 소가 먼저 차례를 진행하여 가장 가까운 소인 $2$번 소를 태그합니다. $2$번 소는 탈락하므로 자기 차례를 갖지 못합니다. 그다음 $3$번 소가 남아 있는 유일한 소인 $1$번 소를 태그합니다. 마지막에 $3$번 소만 남으므로 $3$번 소가 승리합니다.