Футбол#1806

Футбол

10 секунд

64 мегабайти

Дуже легка

У футболі існує багато різних винагород (і покарань), які залежать від вашого місця в турнірній таблиці наприкінці сезону. Наприклад, у Британській Прем'єр-лізі перші $4$ команди можуть грати в Лізі чемпіонів, наступна команда потрапляє до Ліги Європи, а три команди знизу вибувають у нижчу лігу. Зараз сезон добігає кінця, але ще залишилося кілька матчів. Для будь-якої команди потрібно визначити найвище й найнижче місце, яке вона може зайняти в кінці сезону.

У кожному матчі команда перемагає, якщо забила більше голів, ніж суперник. Команда програє, якщо забила менше голів. Якщо обидві команди забили однакову кількість голів, фіксується нічия. За перемогу команда отримує $3$ очки, за нічию — $1$ очко, за поразку — $0$ очок. Команди ранжуються за загальною кількістю очок (більше очок — вище місце). Команди з однаковою кількістю очок ділять одне місце. Наприклад, якщо дві команди поділяють наступний найвищий показник очок після $3$ -ї команди, обидві вони займають $4$ -те місце (а наступна команда — $6$ -те). У реальному житті для визначення місць використовуються додаткові показники, такі як різниця голів, але тут ми їх не враховуємо.

Вам дано список команд і список матчів у сезоні. Припустимо, що кожна команда зіграє однакову кількість матчів до кінця сезону. Деякі матчі вже зіграні й їхні результати відомі.

Вхідні дані

Вхід складається з декількох випадків. Кожен випадок починається з рядка з двох цілих чисел $n$ та $m$ ( $2 \leq n \leq 20$ 2 \leq n \leq 20, $1 \leq m \leq 1000$ 1 \leq m \leq 1000): кількість команд і кількість матчів. Далі йдуть $n$ рядків, у кожному з яких вказано назву команди. Назви команд містять лише літери латиниці й мають довжину не більше $30$ символів. Далі йдуть $m$ рядків у форматі

team1 vs team2: x y

де $t e am 1$ і $t e am 2$ — назви двох різних команд, а $x$ і $y$ — невід'ємні цілі числа (або обидва $- 1$ ), що позначають кількість голів, які забили відповідно $t e am 1$ і $t e am 2$ . Якщо обидва $x$ та $y$ дорівнюють $- 1$ , матч ще не зіграно. Не більше ніж $12$ матчів можуть бути незіграними.

Вхід закінчується, коли $n = m = 0$ n = m = 0.

Вихідні дані

Для кожної команди, у тому ж порядку як у вводі, виведіть один рядок у такому форматі:

Team XXX can finish as high as nth place and as low as mth place.

Замість th використовуйте st, nd, rd для першого, другого й третього місця відповідно. Між випадками виводьте порожній рядок.

Приклади

Приклад 1