Средний чек регионов школьного сайта

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

Первый справочник сопоставляет страницу со школой, а второй справочник сопоставляет школу с регионом. У некоторых страниц школа неизвестна. Кроме того, в логе могут встречаться удалённые страницы, которых уже нет в первом справочнике. Такие посещения не относятся ни к одному региону и при расчёте не учитываются.

В конце входа задан запрос из нескольких регионов. Для каждого региона из запроса требуется вычислить средний чек: сумма сумм заказов всех учтённых посещений региона / количество учтённых посещений региона. Требуется вывести название региона из запроса с наибольшим средним чеком.

Гарантируется, что для каждого региона из запроса найдётся хотя бы одно учтённое посещение. Если наибольший средний чек достигается у нескольких регионов, выводится лексикографически меньшее название региона. Округление не применяется, так как выводится название региона.

Формат ввода

В первой строке записаны четыре целых числа n, p, s, q — число строк лога, число строк первого справочника, число строк второго справочника и число регионов в запросе.

В следующих n строках записаны три значения: visit_id, page_id, amount — идентификатор посещения, идентификатор просмотренной страницы и сумма заказа в рублях.

В следующих p строках записаны два значения: page_id, school_id. Значение school_id, равное -, означает, что школа для страницы неизвестна.

В следующих s строках записаны два значения: school_id, region_name — идентификатор школы и название её региона.

В следующих q строках записаны названия регионов, образующих запрос. Все названия регионов в запросе различны.

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

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

Ограничения

1 ≤ n, p, s ≤ 4000.

1 ≤ q ≤ min(s, p, 4000).

n + p + s ≤ 4000.

1 ≤ amount ≤ 1 000 000.

Длины visit_id, page_id, school_id и region_name составляют от 1 до 20 символов. Идентификаторы и названия не содержат пробелов. Символ - в поле school_id используется только как признак неизвестной школы.

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