Рейтинг тарифов по длительности сбоев

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

Для каждого тарифа требуется найти суммарную длительность всех сбоев по заявкам его абонентов. Заявка с длительностью -1 означает, что данные о длительности не поступили. Такие заявки в сумму не включаются.

Если у тарифа нет заявок с известной длительностью, его суммарная длительность считается равной 0. Необходимо вывести названия трёх тарифов с наибольшими суммарными длительностями, от большего значения к меньшему. При равенстве суммарных длительностей тариф с лексикографически меньшим названием выводится раньше. Округление не выполняется, так как все суммы являются целыми числами.

Формат ввода

В первой строке даны два целых числа n и m — количество абонентов и количество заявок.

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

В следующих m строках записана таблица заявок. Каждая строка содержит три целых числа ticket_id, account_id и outage_minutes — номер заявки, лицевой счёт абонента и длительность сбоя в минутах.

Формат вывода

Выведите три названия тарифов через один пробел в порядке убывания суммарной длительности сбоев.

Ограничения

3 ≤ n ≤ 1000.

0 ≤ m ≤ 2000 - n.

3 ≤ количество различных названий тарифов ≤ n.

1 ≤ account_id ≤ 10^9, все лицевые счета в таблице абонентов различны.

1 ≤ ticket_id ≤ 10^9, все номера заявок различны.

Каждый account_id из таблицы заявок присутствует в таблице абонентов.

Название тарифа состоит из строчных латинских букв и имеет длину от 1 до 20.

outage_minutes равно -1 или является целым числом от 0 до 1440.