Редактор спортивной газеты готовит итоговую таблицу футбольного чемпионата. В чемпионате участвуют n команд, и к моменту верстки уже известны результаты m сыгранных матчей. По этим данным нужно восстановить турнирную таблицу.

За победу команда получает 3 очка, за ничью — 1 очко, за поражение — 0 очков.

Редактор сортирует команды в таблице по следующим правилам, в указанном порядке:

1. По убыванию количества очков.
2. По убыванию разницы забитых и пропущенных мячей.
3. По убыванию количества забитых мячей.
4. По возрастанию названия команды в лексикографическом порядке.

Для каждой команды необходимо посчитать все основные статистические показатели и вывести команды в том порядке, в котором они должны идти в турнирной таблице.

Входные данные

В первой строке даны два целых числа n и m — количество команд и количество уже сыгранных матчей.

В следующих n строках записаны названия команд — по одному в строке. Каждое название состоит из латинских букв и цифр. Все названия различны.

В следующих m строках записаны результаты матчей в формате team1 team2 g1 g2, где:

• team1 и team2 — названия команд;
• g1 — количество мячей, забитых командой team1;
• g2 — количество мячей, забитых командой team2.

Гарантируется, что team1 != team2, и никакие две команды не играли друг с другом более одного раза.

Выходные данные

Выведите n строк — итоговую турнирную таблицу.

В каждой строке через пробел выведите:

название_команды сыграно побед ничьих поражений забито пропущено очки

Команды должны быть упорядочены по правилам сортировки, описанным в условии.

Ограничения

• 1 <= n <= 30
• 0 <= m <= n * (n - 1) / 2
• длина названия команды: от 1 до 20 символов
• 0 <= g1, g2 <= 100

Примеры

Пример 1

Входные данные

1 0
A

Выходные данные

A 0 0 0 0 0 0 0

Пример 2

Входные данные

2 1
B
A
B A 0 0

Выходные данные

A 1 0 1 0 0 0 1
B 1 0 1 0 0 0 1