Тарифы доставки в моменты заказов

Служба доставки еды хранит историю тарифов для зон доставки. Каждый тариф действует в некотором интервале времени и задаёт стоимость доставки в копейках.

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

В конце входа задан запрос: список зон. Необходимо найти суммарную стоимость доставки всех заказов из зон запроса. Повторяющиеся названия зон в запросе учитываются только один раз. Если зона из запроса не встречается среди заказов или тарифов, её вклад равен 0.

Тариф с началом start и концом end действует для заказа со временем time, если start <= time <= end. Для одной зоны интервалы тарифов не пересекаются, поэтому для каждого заказа может подойти не более одного тарифа. При равенстве времени заказа началу или концу интервала тариф действует, обе границы включаются.

Формат ввода

В первой строке даны два целых числа n и m — число записей о тарифах и число заказов.

В следующих n строках содержатся тарифы в формате:

zone start end fee_cents

где zone — название зоны, start и end — начало и конец действия тарифа, fee_cents — стоимость доставки в копейках.

В следующих m строках содержатся заказы в формате:

order_id zone time

где order_id — номер заказа, zone — зона доставки, time — момент оформления заказа.

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

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

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

Ограничения

1 <= n, 1 <= m, n + m <= 4000.

1 <= q <= 100.

0 <= start <= end <= 10^9.

0 <= time <= 10^9.

0 <= fee_cents <= 10^7.

1 <= order_id <= 10^9.

Длина каждого названия зоны от 1 до 12 символов. Названия состоят только из строчных латинских букв.

Для любых двух тарифов одной зоны их замкнутые интервалы времени не пересекаются.