O mulțime de creaturi din Erathia se află în arenă. Ele se vor lupta pentru a demonstra care este cea mai puternică rasă.

    Vrăjitorii din Bracada au teleportat creaturile în diverse poziții ale Arenei. Pentru a putea colabora, două creaturi din acceași rasă pot comunica folosind tehnici ale Școlii de Magie a Spiritului. Totuși, calitatea comunicării telepatice depinde de distanță. Așadar, o rasă va fi dezavantajată dacă două creaturi ale rasei respective se află la distanță mare.

    Se cunosc coordonatele la care au fost teleportate creaturile și trebuie determinată cea mai defavorizată rasă. Cu alte cuvinte, va trebui să determinați, pentru fiecare rasă, distanța maximă dintre doi reprezentanți ai rasei respective și apoi, pe baza distanțelor determinate, să alegeți cea mai defavorizată rasă.

Fișierul de intrare ARENA.IN conține pe prima linie un singur număr natural N, reprezentând numărul creaturilor.

    Pe fiecare dintre următoarele N linii se află trei valori x, y și r, separate prin spații. Primele două valori sunt numere reale și reprezintă coordonatale la care se află creatura, iar cea de-a treia este un șir de caractere care reprezintă rasa creaturii.

Fișierul de ieșire ARENA.OUT trebuie să conțină o singură linie pe care se va afla un șir de caractere reprezentând denumirea rasei celei mai defavorizate.

  • 2 <= N <= 5000;
  • coordonatele creaturilor sunt numere reale cuprinse între 0 și 1000 și conțin cel mult două zecimale exacte;
  • numele creaturilor sunt formate din cel mult 25 de caractere; acestea pot fi litere mici ale alfabetului englezesc sau spații;
  • vor exista cel mult 1000 de rase;
  • pentru fiecare rasă există cel puțin doi reprezentanți.


  • ARENA.IN
    7
    1 1 dragon
    1 2 minotaur
    1 3 wood elf
    1 4 wood elf
    1 5 wood elf
    2 5 minotaur
    2 6 dragon

    ARENA.OUT
    dragon

    Distanța dintre cei doi dragoni este aproximativ 5.099, distanța dintre cei doi minotauri este aproximativ 3.162, iar distanțele dintre elfi sunt 1 sau 2. Așadar, dragonii sunt cei mai defavorizați (doar din punct de vedere al capacității de comunicare!).