Частая метка результата на дистанции

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

Для части исходных меток дана таблица синонимов. Если метка встречается в этой таблице, она заменяется на соответствующую нормализованную метку. Если метки в таблице нет, она уже считается нормализованной. Метка - означает пропуск и не участвует в подсчётах.

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

c_d(x) = число строк результата с дистанцией d, непустой меткой и нормализованной меткой x.

Требуется вывести метку, для которой значение c_d(x) максимально. Если для дистанции из запроса нет ни одной строки с непустой меткой, выводится NONE.

Если наибольшее значение достигается у нескольких меток, выводится лексикографически меньшая метка.

Округление не применяется, так как ответ является строковой меткой.

Формат ввода

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

В следующих n строках записаны два значения: целое число distance и строка raw_label — дистанция в метрах и исходная метка результата.

В следующих m строках записаны две строки: raw_label и canonical_label. Такая строка означает, что исходную метку raw_label нужно заменить на метку canonical_label.

В последних q строках записано по одному целому числу query_distance — дистанции запроса.

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

Выведите q строк. В строке с номером i выведите наиболее частую нормализованную метку для i-й дистанции запроса или NONE, если для неё нет результатов с непустрыми метками.

Ограничения

1 ≤ n ≤ 2000.

1 ≤ m ≤ 30.

1 ≤ q ≤ 20.

50 ≤ distance, query_distance ≤ 10000.

Длина каждой метки, кроме -, составляет от 1 до 20 символов.

Метки состоят из строчных латинских букв и символа подчёркивания.

Исходные метки в словаре синонимов не повторяются.

Метка - встречается только в строках результатов и обозначает пропуск.