Энтропия видов птиц по запросу зон

Сотрудники парка записывают наблюдения за птицами. Для каждого наблюдения известны зона парка и вид птицы. Иногда вид определить не удалось, тогда вместо него записан символ -.

В конце журнала расположен запрос: перечислены зоны, данные из которых нужно объединить. Требуется вычислить энтропию Шеннона распределения видов среди наблюдений из выбранных зон. Наблюдения с неизвестным видом - в расчёт не входят.

Пусть после удаления неизвестных видов осталось m наблюдений, а вид i встретился c_i раз. Его доля равна p_i = c_i / m. Энтропия Шеннона определяется формулой H = -Σ p_i · log2(p_i), где сумма берётся по всем видам с положительной частотой. Если после удаления неизвестных видов наблюдений не осталось, энтропия считается равной 0.

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

Формат ввода

В первой строке дано целое число n — количество наблюдений.

В следующих n строках записаны через пробел название зоны и вид птицы.

В следующей строке дано целое число q — количество названий зон в запросе.

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

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

Выведите одно число — энтропию Шеннона видов птиц среди наблюдений из зон запроса.

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

Ограничения

1 ≤ n ≤ 1000.

1 ≤ q ≤ 20.

Название зоны состоит из строчных латинских букв и имеет длину от 1 до 20.

Название вида состоит из строчных латинских букв и имеет длину от 1 до 20, либо равно символу -.

Каждая зона из запроса встречается хотя бы в одной строке журнала.