Problema A - Controle de Tráfego Aéreo

Finalmente, o local do novo aeroporto de Lisboa está escolhido: Alcochete. Construído de raiz a pensar no futuro, terá um imenso volume de aviões sempre a descolar e a aterrar. Gerir todo este "engarrafamento" aéreo não é nada fácil. A missão dos controladores de tráfego aéreo é precisamente garantir um fluxo de aviões seguro. São eles que, a partir da torre de controlo, fornecem indicações e autorizações de voo, de acordo com as características da aeronave e do contexto do momento. Podem pedir aos pilotos para alterar factores como a rota, a altitude ou a velocidade. Como deves imaginar, todo este trabalho não é completamente manual. Programas de computador muito elaborados auxiliam os controladores e garantem a eficácia do sistema.

Uma empresa que faz software de controlo aéreo contratou-te a ti para ajudar. Um dos muitos sistemas instalados avisa do perigo de colisão entre dois aviões. Se dois aviões estiverem demasiado próximos, um alarme dispara imediatamente. Basicamente, a empresa quer que programes uma maneira eficiente de detectar isto, descobrindo no meio de todo o tráfego aéreo quais são os dois aviões mais próximos um do outro. Como simplificação, as posições dos aviões são dadas como em coordenadas (X,Y), em relação a uma determinada origem. A altitude, direcção e velocidade do avião pode ser ignoradas. Se dois aviões tiverem posições (X₁,Y₁) e (X₂,Y₂), a distância entre eles é dada pela fórmula .

Cada avião é identificado por um código alfanumérico. Um exemplo de um tráfego aéreo seria o que é dado na figura seguinte.

Neste caso, os dois aviões mais próximos seriam o TP420 e o IB260, a uma distância de .

O Problema

Escreve um programa que dadas as localizações (X,Y) de um conjunto de aviões, calcula qual o par de aviões que está mais perto um do outro.

Input

Na primeira linha de input vem um número inteiro A, indicando o número de aviões a considerar (2 ≤ A ≤ 50 000).

Seguem-se exactamente A linhas, cada uma delas indicando um avião no formato "CODIGO X Y" onde CODIGO é uma palavra contendo apenas letras e/ou números (de tamanho máximo 10) e X e Y são as coordenadas da localização do avião (0 ≤ X,Y ≤ 40 000). É garantido que nunca estarão dois aviões exactamente no mesmo ponto.

Output

O output é constituído por uma única linha contendo os códigos do par de aviões que estão mais próximos um do outro, no formato "CODIGO1 CODIGO2". Deve sempre vir primeiro o código do avião que aparecer também primeiro no input.

É garantido que nos casos de teste dados a solução é única, ou seja, existe apenas um par de aviões que está à distância mínima.

Exemplo de Input

6
TP270 1.0 4.0
TP420 2.0 3.0
LF120 3.5 3.5
LF390 3.5 0.5
IB460 1.0 1.0
IB260 2.5 2.0

Exemplo de Output

TP420 IB260