Футбол
У футболі існує багато різних нагород (і покарань) залежно від того, яке місце команда займає в лізі наприкінці сезону. Наприклад, у Британській Прем'єр-лізі перші 4 команди отримують право грати в Лізі чемпіонів, наступна команда отримує право грати в Лізі Європи, а три останні команди вибувають у нижчий дивізіон. Зараз наближається кінець футбольного сезону, і ще залишилося зіграти кілька матчів. Для будь-якої команди ми хочемо визначити, яке найвище та найнижче місце вона може зайняти наприкінці сезону.
За кожну зіграну гру команда перемагає, якщо забиває більше голів, ніж її суперник. Команда програє гру, якщо забиває менше голів. Коли обидві команди забивають однакову кількість голів, це називається нічиєю. Команда отримує 3 очки за кожну перемогу, 1 очко за кожну нічию і 0 очок за кожну поразку. Команди ранжуються відповідно до кількості набраних очок (більше очок означає вищий рейтинг). Команди, які мають однакову кількість очок, отримують однаковий ранг. Наприклад, якщо дві команди мають однакову кількість очок і займають наступне місце після команди, що на 3-му місці, то обидві команди займають 4-те місце (а наступна команда займає 6-те місце). У реальному житті для розв'язання нічиїх використовуються такі фактори, як різниця голів і кількість забитих голів, але ми не будемо враховувати їх у цій задачі.
Вам надано список футбольних команд і список матчів у сезоні. Ви можете припустити, що кожна команда зіграє однакову кількість ігор наприкінці. Деякі з матчів вже зіграні, і результати відомі.
Вхідні дані
Вхідні дані складаються з кількох випадків. Перша строка в кожному випадку містить два цілі числа n та m (2 ≤ n ≤ 20, 1 ≤ m ≤ 1000), що вказують на кількість команд у лізі та кількість матчів у сезоні. Наступні n рядків містять назву кожної команди в окремому рядку. Назви команд містять лише алфавітні символи і мають довжину не більше 30 символів. Це супроводжується m рядками кожного з формату
team1 vs team2: x y
де team1 та team2 є назвами двох різних команд, а x та y є невід'ємними цілими числами (або обидва дорівнюють -1), що вказують на те, що в грі між team1 та team2, team1 забиває x голів, а team2 забиває y голів. Якщо обидва x та y дорівнюють -1, то гра ще не була зіграна. Не більше 12 ігор ще не були зіграні.
Вхідні дані завершуються n = m = 0.
Вихідні дані
Для кожної команди в тому ж порядку, що і список команд у вхідних даних, надрукуйте один рядок наступного формату:
Команда XXX може закінчити на найвищому n-му місці та на найнижчому m-му місці.
Використовуйте st, nd та rd замість th для першого, другого та третього місця відповідно. Надрукуйте порожній рядок між випадками.