Средний чек кормления по регионам

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

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

Для каждого региона вычисляется средний чек кормления по всем строкам журнала с известной стоимостью:

средний чек региона = сумма стоимостей кормлений региона / количество кормлений региона с известной стоимостью.

Если стоимость в журнале обозначена символом -, она неизвестна и в расчёт не включается. Требуется вывести название региона с максимальным средним чеком. Гарантируется, что у каждого региона есть хотя бы одно кормление с известной стоимостью.

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

Формат ввода

В первой строке записаны три целых числа n, a, e — количество строк в журнале кормлений, количество животных в справочнике животных и количество вольеров в справочнике вольеров.

В следующих n строках записаны идентификатор животного и стоимость кормления: animal_id cost. Значение cost — целое неотрицательное число или символ -.

В следующих a строках записаны идентификатор животного и идентификатор его вольера: animal_id enclosure_id.

В следующих e строках записаны идентификатор вольера и название региона: enclosure_id region.

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

Выведите название региона с максимальным средним чеком кормления.

Ограничения

1 ≤ n, a, e.

n + a + e ≤ 4000.

Стоимость известного кормления: целое число от 0 до 1 000 000 включительно.

Длина каждого идентификатора и названия региона — от 1 до 30 символов. Идентификаторы и названия состоят из строчных латинских букв, цифр и символа _.

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

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