Macro-F1 жанров фильмов

Онлайн-кинотеатр проверяет модель, которая определяет жанр фильма. Для каждого фильма известен истинный жанр и результат работы модели.

Входные данные состоят из двух таблиц. Первая таблица содержит истинные жанры, вторая — предсказания модели. Строки таблиц могут идти в разном порядке, поэтому сведения о фильме необходимо сопоставлять по идентификатору film_id.

Возможны три жанра: drama, comedy, documentary. Значение - во второй таблице означает, что модель не выдала предсказание. Такое значение не является жанром: оно увеличивает число ложных отрицаний истинного жанра, но не увеличивает число ложных срабатываний никакого жанра.

Для каждого жанра вычисляется F1-мера: F1 = 2 * TP / (2 * TP + FP + FN), где TP — число верных предсказаний этого жанра, FP — число фильмов, ошибочно предсказанных как этот жанр, а FN — число фильмов этого истинного жанра, не предсказанных как этот жанр. Если знаменатель равен нулю, F1 этого жанра считается равной 0. Требуется вывести macro-F1 — среднее арифметическое F1 для трёх жанров.

При равенстве значений F1 у нескольких жанров никакой один жанр не выбирается: в macro-F1 входят значения всех трёх жанров.

Формат ввода

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

В следующих n строках дана первая таблица: film_id true_genre, где film_id — идентификатор фильма, а true_genre — его истинный жанр.

В следующих n строках дана вторая таблица: film_id predicted_genre, где film_id — идентификатор фильма, а predicted_genre — жанр, предсказанный моделью, либо -.

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

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

Выведите одно число — значение macro-F1, записанное ровно с тремя знаками после десятичной точки.

Ограничения

1 <= n <= 4000.

1 <= film_id <= 10^9.

Идентификаторы фильмов внутри каждой таблицы попарно различны.

Длина каждого жанрового значения составляет от 1 до 11 символов.

Истинный жанр равен одному из значений drama, comedy, documentary.

Предсказанный жанр равен одному из значений drama, comedy, documentary, -.