Порог тревоги для солнечных станций

На солнечных электростанциях система мониторинга оценивает вероятность неисправности инвертора. Для каждой исторической записи известны станция, оценка системы и факт неисправности.

Оценка системы является целым числом от 0 до 1000. Если оценка не была получена, вместо неё записано NA. Такие записи не используются при подсчёте метрики.

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

Для фиксированной станции и порога определяются числа: TP — тревога подана и неисправность была, FP — тревога подана и неисправности не было, FN — тревога не подана, но неисправность была. Метрика F1 определяется формулой F1 = 2·TP / (2·TP + FP + FN). Если знаменатель равен нулю, значение F1 считается равным 0.

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

Формат ввода

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

В следующих n строках даны идентификатор станции station, оценка score и метка fault. Значение fault равно 1, если в записи была неисправность, и 0 иначе. Значение score является целым числом или строкой NA.

В следующей строке записаны k различных целых чисел — допустимые пороги.

В следующих q строках записаны идентификаторы станций из запроса.

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

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

Выводится целое число, округление не выполняется.

Ограничения

1 ≤ n ≤ 4000.

1 ≤ k ≤ 200.

1 ≤ q ≤ 100.

Длина идентификатора станции составляет от 1 до 12 символов и состоит из латинских букв, цифр и символа _.

score равно NA или целому числу от 0 до 1000.

fault равно 0 или 1.

Каждый допустимый порог является целым числом от 0 до 1000, все пороги различны.

Каждая станция из запроса встречается хотя бы в одной исторической записи. Все её записи могут иметь значение score = NA.