1938: Курси валют
Переглянути як PDFВідомі співвідношення між різними грошовими одиницями.
Яка з грошових одиниць найдорожча?
Input
У першому рядку записано ціле число ~K~ - кількість пар грошових одиниць, для яких відомі співвідношення.
У наступних ~K~ рядках записано по одному співвідношенню між грошовими одиницями у форматі '~H~ ~M~ ~L~', де ~H~ і ~L~ - назви, відповідно, більшої і меншої грошових одиниць у вигляді рядка малих англійських букв кожна (до 15 символів); ~M~ - ціле число, кількість менших одиниць у більшій. Для кожної грошової одиниці ~H~ наведено не більше, ніж одне співвідношення. Найдорожча грошова одиниця дорожча від найдешевшої не більше ніж у ~2 \times 10^9~ разів.
Output
Вивести в один рядок назву найдорожчої грошової одиниці. Якщо таких грошових одиниць декілька, то вивести будь-яку назву.
Якщо відповідь відшукати неможливо, то вивести "there is no solution".
Обмеження
~1 \le K < 100~
~1 \le M \le 100~
~1 \le |H|, |L| \le 15~
~H~, ~L~ мiстять символи з промiжку ['a'..'z']
Sample Input 1
2
kp 5 dz
dz 12 kop
Sample Output 1
kp
Коментарі
Чи можуть h повторюватися?
ні. Це слідує з умови
Чи можуть L повторюватися?
так
Чи є задані співвідношення справді валідними співвідношеннями валют? Тобто чи гарантується, що не виявиться, що валюта А більша за Б, яка більша за В, яка більша за А? (Виходить цикл А > Б > В > A)
Чи буде відповідь "there is no solution" у такому тесті: 3 kp 1 dz dz 1 kop kop 1 a
без коментарів