TF-IDF слова в заметке велопоездки

В городском велопрокате после некоторых поездок сохраняются короткие текстовые заметки о маршруте. Например, в заметках могут встречаться слова «центр», «парк», «набережная» и «дождь».

Для поиска необычных слов в конкретной заметке используется мера TF-IDF. Известны заметки всех поездок за день, а в конце входа записан запрос с идентификатором поездки и словом.

Для слова w и заметки поездки d определяется TF(w, d) = c(w, d) / L(d), где c(w, d) — число вхождений слова w в заметку, а L(d) — число слов в ней. Также определяется IDF(w) = ln(n / DF(w)), где n — число поездок, а DF(w) — число заметок, содержащих слово w хотя бы один раз. Требуется вычислить TF-IDF(w, d) = TF(w, d) * IDF(w) для запроса. Если запрошенное слово отсутствует в заметке запрошенной поездки, его TF-IDF считается равным 0, в том числе для пропущенной заметки -. При равенстве каких-либо промежуточных числовых величин никаких вариантов выбирать не требуется.

Формат ввода

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

В следующих n строках даны идентификатор поездки trip_id и заметка о маршруте route_note, разделённые одним или несколькими пробелами. Заметка состоит из слов, разделённых пробелами. Значение - означает, что заметка отсутствует и содержит ноль слов.

В последней строке дан запрос в формате ЗАПРОС trip_id word, где trip_id — идентификатор поездки, а word — искомое слово.

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

Выведите одно число — значение TF-IDF для слова и поездки из запроса.

Число следует вывести ровно с четырьмя знаками после десятичной точки, округлив до четырёх знаков после точки.

Ограничения

1 ≤ n ≤ 2000.

1 ≤ trip_id ≤ 10^9, все идентификаторы поездок различны.

Длина каждого слова составляет от 1 до 20 символов русских строчных букв.

Заметка либо равна -, либо содержит от 1 до 40 слов. Длина непустой заметки не превышает 839 символов.

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

Идентификатор поездки в запросе обязательно присутствует среди данных.