Класс чека по товарам

Супермаркет размечает чеки кодами товарных классов. Например, код food может соответствовать преимущественно продуктовым покупкам, а household — товарам для дома. Для каждого ранее обработанного чека известны код класса и список позиций.

Некоторые позиции могут быть записаны как -: это пропуск, когда название товара не удалось распознать. Такие позиции не учитываются при обучении. В конце входа дан ЗАПРОС — список товаров нового чека. Требуется определить наиболее вероятный код его класса по мультиномиальной модели наивного Байеса с аддитивным сглаживанием 1.

Пусть N_c — число обучающих чеков класса c, T_c — число всех распознанных товарных позиций в чеках класса c, V — число различных распознанных названий товаров во всех обучающих чеках, а count(c, w) — число появлений товара w в чеках класса c. Пусть q(w) — сколько раз товар w встречается в ЗАПРОСЕ. Для каждого класса вычисляется величина

S(c) = ln(N_c / n) + sum по товарам w из ЗАПРОСА q(w) * ln((count(c, w) + 1) / (T_c + V)).

Выводится класс с наибольшим значением S(c). Все товары ЗАПРОСА гарантированно встречаются хотя бы один раз среди распознанных позиций обучающих чеков. Если наибольшее значение достигается у нескольких классов, выводится лексикографически меньшее имя класса. Округление не применяется, так как выводится строковая метка класса.

Формат ввода

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

В следующих n строках записаны чек: код класса class, целое число k и k позиций чека. Каждая позиция является названием товара либо символом -.

В последней строке записаны целое число m и m названий товаров ЗАПРОСА.

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

Выведите единственный код класса для чека из ЗАПРОСА.

Ограничения

1 ≤ n ≤ 4000.

1 ≤ k ≤ 30 для каждого чека.

1 ≤ m ≤ 50.

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

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

Всего в обучающих чеках есть хотя бы одна распознанная товарная позиция. Каждый товар ЗАПРОСА является корректным названием товара и встречается среди распознанных позиций хотя бы одного обучающего чека.