Farmer John a acquis $N$ ($2 \le N \le 2,000$) vaches susceptibles, numérotées $1$..$N$. Elles détestent vraiment être trop proches d’autres vaches. Énormément.

FJ a relevé les coordonnées entières $X_{i}$, $Y_{i}$ de chaque vache $i$ ($1 \le X_{i} \le 100,000; 1 \le Y_{i} \le 100,000$).

Parmi toutes ces vaches, exactement deux sont les plus proches l’une de l’autre. FJ voudrait les éloigner un peu. Déterminez ces deux vaches et affichez leurs numéros ($i$) dans l’ordre numérique.

À titre d’exemple, considérez ce champ de vaches (représenté sur une grille de machine à écrire dont les proportions diffèrent légèrement de celles attendues) :

                    10 | . . . . . . . 3 . . . . .
                     9 | . 1 . . 2 . . . . . . . .
                     8 | . . . . . . . . . . . . .
                     7 | . . . . . . . . . . 4 . .
                     6 | . . . . . . 9 . . . . . .
                     5 | . 8 . . . . . . . . . . .
                     4 | . . . . . 7 . . . . . . .
                     3 | . . . . . . . . . 5 . . .
                     2 | . . . . . . . . . . . . .
                     1 | . . . . 6 . . . . . . . .
                     0 ---------------------------
                                           1 1 1 1
                       0 1 2 3 4 5 6 7 8 9 0 1 2 3

Un rapide examen montre que les vaches $7$ et $9$ sont les plus proches (leur distance est $\mathrm{sqrt}(1*1+2*2) = \mathrm{sqrt}(5)$), donc la sortie serait 7 9 sur une seule ligne (sans guillemets, bien sûr).

Entrée

• Ligne 1 : un seul entier $N$.

• Lignes $2$..$N$+$1$ : la ligne $i$ contient les coordonnées de la vache $i$ sous forme de deux entiers séparés par une espace : $X_{i}$ et $Y_{i}$.

Sortie

• Ligne 1 : les deux numéros de la paire de vaches la plus proche (triés).

Exemples

Entrée 1

9
2 9
5 9
8 10
11 7
10 3
5 1
6 4
2 5
7 6

Sortie 1

7 9

Remarque

Comme dans l’exemple.

Auteur du problème : Rob Kolstad, 2009