Категории книг выше среднего срока выдачи

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

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

Если в записи о выдаче вместо срока указано NA, срок неизвестен. Такая запись не участвует ни в среднем по категории, ни в общем среднем. Категории, для которых нет ни одной выдачи с известным сроком, не выводятся.

Средний срок для набора из k известных значений равен \(\frac{x_1 + x_2 + \ldots + x_k}{k}\). В ответ нужно вывести названия всех категорий, средний срок которых строго больше общего среднего срока, в алфавитном порядке, по одному названию в строке. Если средний срок категории равен общему среднему, эта категория не выводится. Если подходящих категорий нет, следует вывести NONE.

Округление не применяется: сравнение средних выполняется точно, без вывода дробных чисел.

Формат ввода

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

В следующих n строках содержатся записи каталога в формате:

book_id category

Здесь book_id — идентификатор книги, category — название её категории.

В следующих m строках содержатся записи о выдачах в формате:

loan_id book_id days

Здесь loan_id — идентификатор выдачи, book_id — идентификатор выданной книги, days — срок выдачи в днях или строка NA.

Каждый book_id во второй таблице присутствует в первой таблице.

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

Выведите названия подходящих категорий в алфавитном порядке, по одному в строке.

Если подходящих категорий нет, выведите NONE.

Ограничения

• 1 ≤ n ≤ 2000;
• 1 ≤ m ≤ 2000;
• 1 ≤ book_id ≤ 10^9, идентификаторы книг в каталоге различны;
• 1 ≤ loan_id ≤ 10^9, идентификаторы выдач различны;
• days равно NA или целому числу от 1 до 365;
• хотя бы в одной записи о выдаче значение days не равно NA;
• название категории состоит из строчных латинских букв и имеет длину от 1 до 20 символов.